Latest revision as of 00:35, 29 January 2021

Abstract

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" (419-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 multiprocessi ng. 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.

Original document

The different versions of the original document can be found in:

• http://www.cs.kent.edu/~parallel/papers/meilander01.pdf

• http://www.cs.kent.edu/~parallel/papers/meilander01.pdf,

https://dblp.uni-trier.de/db/conf/ipps/ipdps2001.html#MeilanderBP01,

http://doi.ieeecomputersociety.org/10.1109/IPDPS.2001.925204,

https://www.researchgate.net/profile/Johnnie_Baker/publication/220953193_Predictability_for_Real-Time_Command_and_Control/links/02e7e529fa92ee74af000000.pdf?disableCoverPage=true,

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.3856&rep=rep1&type=pdf,

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.3856&rep=rep1&type=pdf,

https://academic.microsoft.com/#/detail/2110623050

• http://xplorestaging.ieee.org/ielx5/7373/20001/00925204.pdf?arnumber=925204,

http://dx.doi.org/10.1109/ipdps.2001.925204