Résumé for Kenneth E. Batcher. Date unknown. Personal information has been redacted.

This paper proposes a solution to air traffic control (ATC) using an enhanced SIMD machine model called an Associative Processor (AP). Our solution differs from previous ATC systems that are designed for MIMD computers and have a great deal of difficulty meeting the predictability requirements for ATC, which are critical for meeting the strict certification standards required for safety critical software components. The proposed AP solution supports accurate predictions of worst case execution times and guarantees all deadlines are met. Furthermore, the software developed based on the AP model is much simpler and smaller in size than the current corresponding ATC software. As the associative processor is built from SIMD hardware, it is considerably cheaper and simpler than the MIMD hardware currently used to support ATC. We have designed a prototype for eight ATC real-time tasks on ClearSpeed CSX600 accelerator that is used to emulate AP. Performance is evaluated in terms of execution time and predictability and is compared to the fastest host-only version implemented using OpenMP on an 8core multiprocessor (MIMD). Our extensive experiments show that the AP implementation meets all deadlines that can be statically scheduled. To the contrary, some tasks miss their deadlines when implemented on MIMD. It is shown that the proposed AP solution will support accurate and meaningful predictions of worst case execution times and will guarantee that all deadlines are met.

The ASC (MSIMD) model for parallel computation supports a generalized version of an associative style of computing that has been used since the introduction of associative SIMD computers in the early 1970's. In particular, this model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to a unique set in a dynamic partition of the processors, and assignment of tasks to the ISs using control parallelism. ASC also allows a network to interconnect the processing elements (PEs). This paper shows how ASC can simulate synchronous PRAM, and the converse. These results provide an important step in defining the power of associative model in terms of PRAM which is the most studied parallel model. Also, these simulations will provide numerous algorithms for ASC by giving an automatic method of converting algorithms from PRAM to ASC.

MASC (for Multiple Associative Computing) is a practical, highly scalable joint control parallel, data parallel model that naturally supports massive parallelism and a wide range of applications. In this paper, we propose efficient algorithms for the MASC model with a 2-D mesh to simulate enhanced meshes, e.g., meshes with multiple broadcasting (MMB), and basic reconfigurable meshes (BRM). The results not only show the power of the MASC model in terms of the enhanced mesh models but also provide an automatic conversion of numerous algorithms designed for enhanced meshes to the MASC model.

MASC (for Multiple Associative Computing) is a joint control parallel, data parallel model that provides a practical, highly scalable model that naturally supports small to massive parallelism and a wide range of applications. In this paper, we present efficient algorithms for a MASC model with a 2-D mesh to simulate enhanced meshes. Let MASC(n, j) denote a MASC model with n processing elements and j instruction streams. It is shown that a MASC(n, j) model with a 2-D mesh is strictly more powerful than a √n × √n MMB (Mesh with Multiple Broadcasting) when j =Ω(√n ). Simulation of a √n × √n MMB by MASC(n, j) with a 2-D mesh runs in O(1) time and requires no extra memory. Simulating a √n × √n BRM (Basic Reconfigurable Mesh) with MASC(n, j) with a 2-D mesh takes O(√n) extra time with O(n) extra memory when j =Ω(√n ). The reverse simulations of MMB or BRM with MASC with a 2-D mesh is also given. These simulations not only provide information about the power of the MASC model and also provide an automatic conversion of numerous algorithms designed for enhanced meshes to the MASC model.

This paper describes a parallelization of the sequential dynamic programming method for solving a 2D knapsack problem where multiples of n rectangular objects are optimally packed into a knapsack of size L × W and are only obtainable with guillotine-type (side to side) cuts. The parallel algorithm is described and analyzed for the associative model. The associative model (ASC) for parallel computation supports a generalized version of an associative style of computing that has been used since the introduction of associative SIMD computers in the early 1970's. In particular, this model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to an equal number of partition sets of processors, and assignment of tasks to the ISs using control parallelism. This algorithm runs in O(W(n+L+W)) time using O(L) processors, where L ≥ W for a 2D knapsack problem with a capacity of L × W. This result is cost optimal with respect to the best sequential implementation. Moreover, an efficient ASC algorithm for this well-known problem should give insight to how the associative model compares to other parallel models.