Collected works of Kenneth E. Batcher, emeritus professor, and works inspired by his research and scholarship.
Browse the Kenneth E. Batcher Collection: Papers from the Parallel and Associative Computing Laboratory Collections
System Design and Algorithmic Development for Air Traffic Control Based on Associative ProcessorThis paper proposes a 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 AP 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. Experimental results comparing MIMD and CSX600 approaches are presented, and show that our solution can guarantee 8 real-time ATC tasks to be finished within their hard deadlines for a large scale of aircraft. The performance of CSX600 has better scalability, efficiency, and predictability than that of MIMD. |
The Architecture of Tomorrow's Massively Parallel Computer07/01/1987Transcribed from an after-dinner talk given by Dr. Ken Batcher, Goodyear Aerospace Corporation, on September 24, 1986. |
The Flip Network in STARAN1976The flip network in each array module of STARAN scrambles and unscrambles multidimensional access (MDA) memory data. The flip network can permute data on transfers from memory to PE's (processing elements), from PE's to memory, and from PE's to PE's. Among the allowable permutations are barrel shifts, barrel shifts on substrings, and FFT-butterflies. The network can be used for such data manipulations as shifting, mirroring (flipping end-for-end), irregular spreading, or compressing and replicating. These manipulators are useful for sorting, fast Fourier transforms, image warping, and solving partial differential equations on multi-mesh regions. |
The Multidimensional Access Memory in STARAN02/1977STARAN® has a number of array modules, each with a multidimensional access (MDA) memory. The implementation of this memory with random-access memory (RAM) chips is described. Because data can be accessed in either the word direction or the bit-slice direction, associative processing is possible without the need for costly, custom-made logic-in-memory chips. |
The universality of various types of SIMD machine interconnection networks03/1977SIMD machine architects must choose an interconnection network to provide interprocessor communication. The universality of a network is its ability to simulate arbitrary interconnections of the processing elements. We examine the universality of five particular networks which cover the types used in the llliac IV, STARAN, Omen, SlMDA, and RAP machines. They also cover the types discussed by Feng, Lang, Lawrie, Orcutt, Siegel, and Stone. We give O((log2N)2 ) algorithms, where N is the number of processing elements, for the Perfect Shuffle, PM21, WPM21, and Cube networks to simulate arbitrary interconnections (Orcutt has given an O(Nl/2log2N) algorithm for the llliac network). We analyze Batcher's bitonic sorting method and show how each network can implement it on an SIMD machine. We discuss how sorting destination tags is equivalent to simulating interconnections. |
Timings for Associative Operations on the MASC Model2001The MASC (Multiple Associative Computing) model is a generalized associative-style computational model that naturally supports massive data-parallelism and also control-parallelism. A wide range of applications has been developed on this model. Recent research has compared its power to the power of other popular parallel models such as the PRAM and MMB models using simulations. However, the simulation of MMB has identified some important issues regarding the cost of certain basic MASC operations required for associative computing such as broadcasts, reductions, and associative searches. This paper investigates these issues and gives background information and an analysis of timings for these operations, based on implementation techniques and comparison fairness with respect to other models. It aims to provide justification and clarify arguments on the timings for these constant-time or nearly constant-time basic MASC operations. |
Tractable Real-Time Air Traffic Control Automation2002A different paradigm is needed for real-time command and control (C&C) problems. Past approaches, using multiprocessors (MP), for real-time computing have had great difficulty in meeting real problem requirements. We review some reasons why C&C problems that require a solution on a MP architecture may be intractable, and then show an architecture where these reasons for intractability are nonexistent. We describe a polynomial time solution to the air traffic control (ATC) problem, which is a typical C&C problem. This solution uses a static, non-preemptive table driven schedule using a SIMD architecture called an associative processor (AP). The AP is an ideal processor for set and database operations since its single thread instruction stream can operate on an entire set of data with each instruction. The AP eliminates multi-thread instructions, which account for much of the MP intractability mentioned above. |
Using the UML to Describe the BSP Model of Parallel Computation06/2002A Unified Modeling Language (UML) description of the BSP model of parallel computation is presented. This UML description identifies BSP classes and objects and specifies various object and inter-object relationships, dependencies, and behaviors. This was achieved by describing various views of the BSP model using many of the UML structural and behavioral diagrams. The use to the UML to describe the BSP model has been highly effective for further parallel modeling techniques, comparisons to other parallel models, BSP parallel system software research, and BSP algorithm development. |