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
Multiple Instruction Stream Control for an Associative Model of Parallel Computation2003This paper describes a system software design for multiple instruction stream control in a massively parallel associative computing environment. The purpose of providing multiple instruction stream control is to increase throughput and reduce the amount of parallel slackness inherent in single instruction stream parallel programming constructs. The multiple associative computing (MASC) model is used to describe this technique and a brief introduction to the MASC model of parallel computation is presented. A simple parallel computing example is used to illustrate the techniques for multiple instruction stream control in a massively parallel runtime environment. |
On using the UML to describe the MASC model of parallel computation06/2000A Unified Modeling Language (UML) description of the MASC model of parallel computation is presented. This UML description identifies MASC objects and specifies various object and inter-object relationships, dependencies, and behaviors. This was achieved by describing various views of the MASC model by using many of the UML structural and behavioral diagrams. The use of using UML to describe MASC has been highly effective for further parallel modeling techniques, comparisons to other parallel models, MASC parallel system software research, and MASC algorithm development. |
Overview of Air Traffic Control Using an SIMD COTS System2005Air traffic control is an important application with demanding real-time database processing requirements. Systems that have been implemented using current approaches have typically been expensive, late, over-budget and have not performed up to specification. In part this is because, in attempting to meet the real-time requirements, developers have been driven to use complex algorithms and software for what are inherently relatively simple requirements. Our analysis indicates that the use of modern SIMD COTS systems enables guaranteed real-time performance to be achieved with simpler algorithms on modest amounts of hardware. This paper covers the system, the approach to the application and some of the solution details. |
Predictability for Real-Time Command and Control2001This paper describes a new and different paradigm for real-time command and control that we show can provide a static, polynomial-time scheduling algorithm. Current efforts in real-time scheduling have been unable to predict system performance, and use a unpredictable "dynamic" scheduling algorithm. The Nation’s Air Traffic Control (ATC) System has been unable to satisfy performance requirements, and is extremely expensive. An editorial in "USA Today" (4-19-1999) cites expenditures in ATC at $41 billion. But, current multiprocessor technology cannot do the job. The FAA wisely required a “proof of concept” study before the (AAS) contract. But that study, after expending a billion dollars, was abandoned, and production moved forward. AAS was canceled in 1995 exactly in line with real-time scheduling theory predictions. Garey, Graham, and Johnson state: "For these scheduling problems, no efficient optimization algorithm has yet been found, and indeed, none is expected.”[9]. Stankovic et. al. state: "… complexity results show most real-time multiprocessing scheduling is NP-hard.” [6]. We offer a completely different approach, that has been shown to overcome the severe limitations of multiprocessing. Additionally, we show that real-time parallel-processing techniques can be statically scheduled to solve the set of tasks making up the ATC problem for a worst-case environment. |
Predictable Real-Time Scheduling for Air Traffic Control2002A different approach for real-time Command and Control problems is presented, using the Air Traffic Control problem as an example. Current ATC approaches use “dynamic” scheduling algorithms, which by their very nature are unpredictable. The current ATC approach is extremely expensive. The April 19, 1999 issue of USA Today places the cost at $41 billion, and the system is not meeting current specifications. The current problems with ATC are predicted by theoretical results in Real-Time Scheduling. M. Klein et al state “an efficient real-time multiprocessor scheduling algorithm is not expected” [1]. J. Stankovic, [5] indicates that a polynomial time multiprocessor schedule for a C&C problem like ATC is unlikely. Our approach uses synchronous set processing of jobs in this real-time database problem and embodies the qualities of speed, predictability, adaptability and reliability. We show that an associative SIMD processor (AP) using synchronous set processing can complete all ATC tasks before their deadline. |
Real-Time Scheduling in Command and Control1999Real-time tasks for command and control systems are too large or too complex for one processor to handle. Simply adding more CPUs does not result in a linear increase in performance. Current comparative analysis of parallel algorithms does not accurately reflect the increased cost of scheduling when more processors are added. A case is made that associative processors effectively handle real-time command and control type problems and avoid most of the difficulties introduced by multiprocessors. These results suggest that when comparing different architectures, comparative analysis should consider the ALU and control unit {CU} separately. |
Relating the power of the Multiple Associative Computing (MASC) model to that of reconfigurable bus-based models05/2010The MASC (Multiple ASsociative Computing) model is a multi-SIMD model that uses control parallelism to coordinate the interaction of data parallel threads and supports associative SIMD computing on each of its threads. There have been a wide range of algorithms developed for this model. Research on using this model in real-time system applications and building a scalable MASC architecture is currently quite active. In this paper, we present simulations between MASC and reconfigurable bus-based models, e.g., various versions of the Reconfigurable Multiple Bus Machine (RMBM). Constant time simulations of the basic RMBM by MASC and vice versa are obtained. Simulations of the segmenting RMBM, fusing RMBM, and extended RMBM by MASC in non-constant time are also discussed. By taking advantage of previously established relationships between RMBM and two other popular parallel computational models, namely, the Reconfigurable Mesh (RM) and the Parallel Random Access Machine (PRAM), we extend our simulation results to further categorize the power of the MASC model in relation to RM and PRAM. |
Scalable and Efficient Associative Processor Solution to Guarantee Real-Time Requirements for Air Traffic Control Systems05/2012This 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. |
Simulating PRAM with a MSIMD model (ASC)08/14/1998The 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. |
Simulation between enhanced meshes and the multiple associative computing (MASC) model11/1999MASC (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. |