Abstract
With the advent of GPU programmability, many applications have transferred computational intensive tasks into it. Some of them compute intermediate data comprised by a mixture of relevant and irrelevant elements in respect to further processing tasks. Hence, the ability to discard irrelevant data and preserve the relevant portion is a desired feature, with benefits on further computational effort, memory and communication bandwidth. Parallel stream compaction is an operation that, given a discriminator, is able to output the valid elements discarding the rest. In this paper we contribute two original algorithms for parallel stream compaction on the GPU. We tested and compared our proposals with state-of-art algorithms against different data-sets. Results demonstrate that our proposals can outperform prior algorithms. Result analysis also demonstrate that there is not a best algorithm for all data distributions and that such optimal setting is difficult to be achieved without prior knowledge of the data characteristics.

Abstract
Stream Compaction is an important task to perform in the context of data parallel computing, useful for many applications in Computer Graphics as well as for general purpose computation on graphics hardware. Given a data stream containing irrelevant elements, stream compaction outputs a stream comprised by the relevant elements, discarding the rest. The compaction mechanism has the potential to enable savings on further processing, memory storage and communication bandwidth. Traditionally, stream compaction is defined as a monotonic (or stable) operation in the sense that it preserves the relative order of the data. This is not a full requirement for many applications, therefore we distinguish between monotonic and non-monotonic algorithms. The latter motivated us to introduce the Jumping Jack algorithm as a new algorithm for non-monotonic compaction. In this paper, experimental results are presented and discussed showing that, although simple, the algorithm has interesting properties that enable it to perform faster than existent state-of-the-art algorithms, in many circumstances.

Abstract

Abstract

Abstract
Humanoid soccer robots must be able to carry out their tasks in a highly dynamic environment which requires responsive omnidirectional walking. This paper explains a new omnidirectional walking engine for a humanoid soccer robot that mainly consists of a foot planner, a zero moment point (ZMP) trajectory generator, a centre of mass (CoM) calculator and an active balance feedback loop. An analytical approach is presented for generating the CoM trajectory, in which the cart-table motion of the equations is solved using the Fourier approximation of the ZMP. With this approach, we propose using a new time segmentation approach in order to parametrize the double-support phase. An active balance method is also proposed which keeps the robot's trunk upright when faced with environmental disturbances. The walking engine is tested on both simulated and real NAO robots. Our results are encouraging given the fact that the robot performs favourably, walking quickly and in a stable manner in any direction in comparison with the best RoboCup 3D soccer simulation teams for which the same simulator is used. In addition, the proposed analytical Fourier-based approach is compared with the well-established numerical ZMP dynamics control method. Our results show that the presented analytical approach involves less time and complexity and better accuracy compared with the ZMP preview control method.

Abstract