Planar point sets with large minimum convex decompositions

We show the existence of sets with n points (n ? 4) for which every convex decomposition contains more than (35/32)n?(3/2) polygons,which refutes the conjecture that for every set of n points there is a convex decomposition with at most n+C polygons. For sets having exactly three extreme pointswe show that more than n+sqr(2(n ? 3))?4 polygons may be necessary to form a convex decomposition.

Pipelined Radix- 2k Feedforward FFT Architectures

The appearance of radix-$2^{2}$ was a milestone in the design of pipelined FFT hardware architectures. Later, radix-$2^{2}$ was extended to radix-$2^{k}$ . However, radix-$2^{k}$ was only proposed for single-path delay feedback (SDF) architectures, but not for feedforward ones, also called multi-path delay commutator (MDC). This paper presents the radix-$2^{k}$ feedforward (MDC) FFT architectures. In feedforward architectures radix-$2^{k}$ can be used for any number of parallel samples which is a power of two. Furthermore, both decimation in frequency (DIF) and decimation in time (DIT) decompositions can be used. In addition to this, the designs can achieve very high throughputs, which makes them suitable for the most demanding applications. Indeed, the proposed radix-$2^{k}$ feedforward architectures require fewer hardware resources than parallel feedback ones, also called multi-path delay feedback (MDF), when several samples in parallel must be processed. As a result, the proposed radix-$2^{k}$ feedforward architectures not only offer an attractive solution for current applications, but also open up a new research line on feedforward structures.

Mesh traversal and sorting for efficient memory usage in scientific codes

Applications that operate on meshes are very popular in High Performance Computing (HPC) environments. In the past, many techniques have been developed in order to optimize the memory accesses for these datasets. Different loop transformations and domain decompositions are com- monly used for structured meshes. However, unstructured grids are more challenging. The memory accesses, based on the mesh connectivity, do not map well to the usual lin- ear memory model. This work presents a method to improve the memory performance which is suitable for HPC codes that operate on meshes. We develop a method to adjust the sequence in which the data are used inside the algorithm, by means of traversing and sorting the mesh. This sorted mesh can be transferred sequentially to the lower memory levels and allows for minimum data transfer requirements. The method also reduces the lower memory requirements dra- matically: up to 63% of the L1 cache misses are removed in a traditional cache system. We have obtained speedups of up to 2.58 on memory operations as measured in a general- purpose CPU. An improvement is also observed with se- quential access memories, where we have observed reduc- tions of up to 99% in the required low-level memory size.

Flow around a hemisphere-cylinder at high angle of attack and low Reynolds number. Part I: Experimental and numerical investigation

Three-dimensional Direct Numerical Simulations combined with Particle Image Velocimetry experiments have been performed on a hemisphere-cylinder at Reynolds number 1000 and angle of attack 20◦. At these flow conditions, a pair of vortices, so-called “horn” vortices, are found to be associated with flow separation. In order to understand the highly complex phenomena associated with this fully threedimensional massively separated flow, different structural analysis techniques have been employed: Proper Orthogonal and Dynamic Mode Decompositions, POD and DMD, respectively, as well as criticalpoint theory. A single dominant frequency associated with the von Karman vortex shedding has been identified in both the experimental and the numerical results. POD and DMD modes associated with this frequency were recovered in the analysis. Flow separation was also found to be intrinsically linked to the observed modes. On the other hand, critical-point theory has been applied in order to highlight possible links of the topology patterns over the surface of the body with the computed modes. Critical points and separation lines on the body surface show in detail the presence of different flow patterns in the base flow: a three-dimensional separation bubble and two pairs of unsteady vortices systems, the horn vortices, mentioned before, and the so-called “leeward” vortices. The horn vortices emerge perpendicularly from the body surface at the separation region. On the other hand, the leeward vortices are originated downstream of the separation bubble, as a result of the boundary layer separation. The frequencies associated with these vortical structures have been quantified.