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.