A 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.

Air 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.

This 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. 

A 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 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.

The 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.