Acceptance letter to Mr. K. E. Batcher for selection of a paper "for presentation at the 1968 Spring Joint Computer Conference" by the American Federation of Information Processing Societies (AFIPS) in Atlantic City, New Jersey, April 30 - May 2, 1968.

This paper presents a new parallel algorithm for the dynamic convex hull problem. This algorithm is a parallel adaptation of the Jarvis March Algorithm. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers.

This paper will present the implementation and comparison of new parallel algorithms for the convex hull problem. These algorithms are a parallel adaptation of the Jarvis March and the Quickhull algorithms. The computational model selected for these algorithms is the associative computing model (ASC) and the multiple associative computing model (MASC). Both models support massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on many SIMD computers. These algorithms requires O(n) space, O(log n) (i.e., O(log₂ n)) average running time, and O(n) worst case running time. These algorithms have been compared using random data.

This paper presents a new parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham Scan Algorithm. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers. This algorithm requires O(n) space, O(n log n) average cost, and O(n²) worst case cost. The algorithm has been implemented and tested on random data.

This paper presents a new static and dynamic recursive parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham scan and Quick Hull algorithms. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers. The static algorithm requires O(n) space, O(log n) average case running time, and O(n) worst case running time. If O(log n) ISs are used the, static algorithm should have an average running time of O(log log n).

This paper proposes a SIMD solution to air traffic control (ATC) using an enhanced SIMD machine model called an Associative Processor (AP). This 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 SIMD solution will support accurate and meaningful predictions of worst case execution times and will guarantee all deadlines are met. Also, the software will be much simpler and smaller in size than the current corresponding ATC software. An important consequence of these features is that the V&V (Validation and Verification) process will be considerably simpler than for current ATC software. Additionally, the associative processor is enhanced SIMD hardware and is considerably cheaper and simpler than the MIMD hardware currently used to support ATC. The ClearSpeed CSX600 accelerator is used to emulate the AP model. A preliminary implementation of the proposed method has been developed and experimental results comparing MIMD and CSX600 approaches are presented. The performance of CSX600 has better scalability, efficiency, and predictability than that of MIMD.