Open Access Kent State (OAKS)

ASC (associative computing model) and MASC (multiple associative computing model) have long been studied in the Department of Computer Science at Kent State University. While the previous studies provide the background and the basic definition of the model, the description of the interactions between the instruction streams (ISs) is very brief, high level, and incomplete. One change here is that we specify the interaction between ISs and consider that all of the ISs operate on the same clock in order to support predictable worst case computation times, while earlier the ISs were assumed to interact in a MIMD type fashion. This paper provides a detailed explanation as to how these interactions can be supported in the case where only a few ISs are supported.

This paper describes the implementation and use of a dedicated associative SIMD co-processor ideally suited for many applications such as database processing, image processing, genome matching, or molecular similarity analysis. The concept of associative SIMD processing is introduced, and differentiated from other associative and SIMD techniques. Then our ASC (ASsociative Computing) processor is briefly described, along with its implementation of associative SIMD processing. Finally, we demonstrate the use of our ASC processor on relational database processing and on the image processing operation of edge detection.

This paper describes the FPGA implementation of a specialized SIMD processor array for embedded applications. An alternative to traditional SoC or MPSoC architectures, this array combines the massive  parallelism inherent in SIMD architectures with the search capabilities of associative computing, producing a SIMD Processor Array System on a Chip (PASoC) well suited for applications such as data mining and bioinformatics. This paper first describes the architecture of the system, and then the pipelining of the processing elements and the addition of a reconfigurable interconnection network. Finally, the paper concludes with a brief description of a string-matching algorithm that can be used for the applications cited above.

This dissertation has two complementary focuses. First, it provides a solution to large scale real-time system air traffic Control (ATC) using an enhanced SIMD machine model called an associative processor (AP). The second is the comparison of this implementation with a multiprocessor implementation and the implications of these comparisons. This paper demonstrates how one application, ATC, can more easily, more simply, and more efficiently be implemented on an AP than is generally possible on other types of traditional hardware. The AP implementation of ATC will take advantage of its deterministic hardware to use static scheduling. 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. While APs were used for ATC-type applications earlier, these are no longer available. We use a ClearSpeed CSX600 accelerator to emulate the AP solutions of ATC on an ATC prototype consisting of eight data-intensive ATC real-time tasks. Its performance is evaluated in terms of execution time and predictability and is compared with an 8-core multiprocessor (MP) using OpenMP. Our extensive experiments show that the AP implementation meets all deadlines while the MP will regularly miss a large number of deadlines. It is shown that the proposed AP solution will support accurate predictions of worst case execution times and will guarantee that all deadlines are met. In addition, the AP code will be similar in size to sequential code for the same tasks and will avoid all of the additional support software needed with an MP to handle dynamic scheduling, load balancing, shared resource management, race conditions, and false sharing, etc. At this point, essentially only MIMD systems are built. Many of the advantages of using an AP to solve an ATC problem would carry over to other applications. AP solutions for a wide variety of applications will be cited in this paper. Applications that involve a high degree of data parallelism such as database management, text processing, image processing, graph processing, bioinformatics, weather modeling, managing UAS (Unmanned Aircraft Systems or drones) etc, are good candidates for AP solutions. This raises the issue of whether we should routinely consider using non-multiprocessor hardware like the AP for applications where substantially simpler software solutions will normally exist. It also raises the question of whether the use of both AP and MIMD hardware in the same system could provide more versatility and efficiency. Either the AP or MIMD could serve as the primary system but could hand off jobs it could not handle efficiently to the other system.

The Multiple Associative Computing (MASC) parallel model is a generalization model of an Associative Computing (ASC) parallel model designed to support multiple ASC data parallel threads by using control parallelism. The MASC model is designed to combine the advantages of both Single Instruction Stream Multiple Data Streams (SIMD) and Multiple Instruction Streams Multiple Data Streams (MIMD) models. Here is the first time that a complete description of MASC model has been implemented (in software) true to its original description. A cycle precision simulator is built to demonstrate the performance of MASC on various multithreaded algorithms. The simulator is a software prototype for the model with sufficient software details to allow it to be converted into a hardware prototype of the model. If a reasonable limit for the number of threads simultaneously supported is assumed, the resulting hardware design is not only easily to implement, but can easily support a huge number of processing units and is a excellent candidate architecture for supporting large scale (e.g., terascale and petascale) computing. Experimental results shows that, when processing large-scale instances using multiple workers, the algorithm executed by the MASC model using a static task assignment scheme provides strong scaling with constant time overhead.

Goodyear Aerospace Corporation technical report AP-122364

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.