International Journal of High Speed Computing

Details of object recognition as applied to a shared memory multiprocessor system is presented, along with the software for image pre-processing; separation of the object from background; and the calculation of the invariant characteristic of the object using the Hu-invariant technique. Partitioning of the sequential algorithms for implementation in the multiprocessor hardware by the determination of precedence and data dependency, is also described.

A crucial problem in parallelizing compiler design is the choice of a suitable Intermediate Representation (IR) to make parallelism detection and extraction easy and possible. Dependence graphs have long been recognized as useful tools for this aim. Several versions were proposed [1,4,6,20], which encapsulate relations of data dependence, control dependence or both. They were also used in conventional optimizations, but always coupled with the traditional Control Flow Graph (CFG). However, it would be preferable to apply both conventional and parallelizing optimizations to the same IR. Recently, some attempts were made to use dependence graphs as a unifying framework on which all types of optimization [4] are applied. This is one of the aims of our work in this research area. We started working on the well known Hierarchical Task Graph (HTG) of Polychronopoulos and Girkar [6,7,8]. The HTG, by definition, is an acyclic and then a reducible graph. In fact it is built from a CFG arranged hierarchically around loops with all loop back edges removed. This CFG is then enriched with control and data dependence information (edges). Our proposal is an extension of the HTG, named Extended Hierarchical Task Graph (EHTG), that is a HTG where data dependence edges are annotated with a boolean branch path expression indicating the CFG paths through which the data dependences are established. We developed two algorithms of constant propagation (used for dead code elimination) running directly on our EHTG without using the traditional CFG. The two algorithms can be applied only to sequential programs whose parallelism is represented by the HTG structure. They are not suited to perform constant propagation on explicitly parallel programs [12]. Complexity and correctness of the algorithms are analyzed and we also prove that one of them has the same complexity and finds the same class of constants as the well known Wegman & Zadeck constant propagation algorithm [20], that uses a hybrid sparse representation.

We consider diagonal-implicitly iterated Runge–Kutta methods which are one-step methods for stiff ordinary differential equations providing embedded solutions for stepsize control. In these methods, algorithmic parallelism is introduced at the expense of additional computations. In this paper, we concentrate on the algorithmic structure of these Runge–Kutta methods and consider several parallel variants of the method exploiting algorithmic and data parallelism in different ways. Our aim is to investigate whether these variants lead to good performance on current distributed memory machines such as the Intel Paragon and the IBM SP2. As test application we use ordinary differential equations with dense and sparse right-hand side functions.

The 3D Finite-Difference Time-Domain (FDTD) method is a powerful numerical technique for directly solving Maxwell's equations. This paper describes its implementation on high speed computers. This technique is used here for the analysis of millimeter wave planar antennas. In our algorithm, Bérenger's Perfectly Matched Layers (PML) are implemented as absorbing boundary conditions to mimic free space. Dielectric and metallic losses are taken into account in a recursive and dispersive formulation. We present the main techniques implemented to optimize the non-sequential program on vector computers. Besides, two parallel supercomputers of different architectures as well as a multi-user network of Sun workstations are used to investigate the parallel FDTD code. The performances obtained on vector/distributed memory massively parallel/hybrid computers show that the FDTD algorithm is ideally suited for the implementations on both vector and parallel computers. Comparisons with experimental results in the millimeter wave frequency band validate our codes.