Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

Automatic parallelization of irregular and pointer-based computations: perspectives from logic and constraint programming

Irregular computations pose some of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. In the past decade there has been significant progress in the development of parallelizing compilers for logic programming and, more recently, constraint programming. The typical applications of these paradigms frequently involve irregular computations, which arguably makes the techniques used in these compilers potentially interesting. In this paper we introduce in a tutorial way some of the problems faced by parallelizing compilers for logic and constraint programs. These include the need for inter-procedural pointer aliasing analysis for independence detection and having to manage speculative and irregular computations through task granularity control and dynamic task allocation. We also provide pointers to some of the progress made in these áreas. In the associated talk we demónstrate representatives of several generations of these parallelizing compilers.

Untainted puncturing for irregular low-density parity-check codes

Puncturing is a well-known coding technique widely used for constructing rate-compatible codes. In this paper, we consider the problem of puncturing low-density parity-check codes and propose a new algorithm for intentional puncturing. The algorithm is based on the puncturing of untainted symbols, i.e. nodes with no punctured symbols within their neighboring set. It is shown that the algorithm proposed here performs better than previous proposals for a range of coding rates and short proportions of punctured symbols.

The Irregular Ribbed Vault of the Sacristy of the Cathedral of Saint-Jean Baptiste in Perpignan

The vault of the sacristy of the Cathedral of Saint-Jean Baptiste in Perpignan (France), constructed by the Majorcan architect Guillem Sagrera between 1433 and 1447, is an outstanding, yet strikingly unknown, example of rib vaulting. This paper analyzes the overall construction of the form of the vault, characterized by its highly irregular perimeter, with particular attention to an isolated decorated corbel which solves the problem of the wall support of a group of six ribs and is in stark contrast with the rest of the supports, which are completely unadorned. Given the extreme rigour of Sagrera in all his works (and this one in particular), this apparent “capriccio” must be justified not only by decorative or formal requirements, but also by the constructive logic of Gothic vaulting system

Analysis of irregular behaviour on an optical computing logic cell

A new methodology to study irregular behaviours in logic cells is reported. It is based on two types of diagrams, namely phase and working diagrams. Sets of four bits are grouped and represented by their hexadecimal equivalent. Some hexadecimal numbers correspond to certain logic functions. The influence of the internal and external tolerances, namely those appearing in the employed devices and in the working signals, may be analysed with this method. Its importance in the case of logic structures with chaotic behaviours is studied.

Extension of Euskalduna Conference Centre and Concert Hall: A Contemporary Application of Irregular Reciprocal Frames

Reciprocal frame structures, formed by a set of self-supported elements in a closed circuit, have long been used since antiquity to cover large spans with small elements. The roof structure of the Euskalduna conference centre and concert hall extension in Bilbao, covering an irregu- lar geometry of 3000 m2 with a maximum span of 45 m, presented an interesting opportunity to revisit the concept and to apply these classical systems. Furthermore, its analysis and develop- ment led to an interesting discussion on reciprocal frames. They showed great sensitivity of these systems to the local modification of a particular element, establishment of irregular load paths, mobilisation of almost the entire sys- tem when locally applying a punctual load and, finally, its large deformability. Besides, reciprocal frames present particular construction complexities and possibilities due to the moderate length of the structural elements, the predominance of shear-only connec- tions and the necessity of the entire system to be completely erected to guarantee its stability. Euskalduna extension, completed in 2012, is one of the largest and a very par- ticular case of irregular reciprocal frame structures built in the world. It shows the formal possibilities and potentiality of reciprocal frames to respond to free and irregular geometries.

Efficient Irregular Tessellations

Investigación sobre teselaciones irregulares eficientes, con la aplicación en la construcción de un prototipo físico. El prototipo es un casquete semiesférico de 2m de diámetro desarrollado con herramientas de diseño paramétrico y fabricación digital.

Emulation of an OWC Ocean Energy Plant With PMSG and Irregular Wave Model

Ocean energy is a promising resource for renewable electricity generation that presents many advantages, such as being more predictable than wind energy, but also some disadvantages such as large and slow amplitude variations in the generated power. This paper presents a hardware-in-the-loop prototype that allows the study of the electric power profile generated by a wave power plant based on the oscillating water column (OWC) principle. In particular, it facilitates the development of new solutions to improve the intermittent profile of the power fed into the grid or the test of the OWC behavior when facing a voltage dip. Also, to obtain a more realistic model behavior, statistical models of real waves have been implemented.