A New Paradigm For Real-Time Database Management (Non-Refereed)
Will C. Meilander · 2007
Garey and Johnson in their highly respected text write: “There is wide agreement that a problem is not ‘well solved’ until a polynomial time algorithm is known for it.” Such a “well solved” polynomial time algorithm is the subject of this paper. We show the ATC environment and consequently the database and solution to be polynomial. Real-time database management (RTDB) has for many years been declared NP-hard or NP-complete for a multiprocessor (MP). We agree. Results achieved in practice support that claim. The approach offered here uses, the associative processor (AP), in which a static program providing a “well solved” solution for many realtime databases can be realized. A major military program, the US Navy’s E2C AEW system started using this approach in 1983. The AP called “ASPRO” had 2,000 processing elements and showed a measured throughput improvement of 274 times over the dual processor approach it replaced. Equivalent E2C radar tracking performance has not been achieved in our air traffic control system. The AP is SIMD architecture, as described in my companion abstract “3-D Real-time Database”. However, because any RTDB system requires high speed I/O, the AP has a multidimensional access memory (MDA) that implements the required I/O performance. Many other SIMD machines developed over the past 35 years could not provide adequate I/O for the RTDB requirements. Why does the AP handle RTDB problems so much better than the MPs currently in use? There are two parts to the answer. First the AP can implement the RTDB as a 3-D structure, suggested in Codd’s twelve rules for relational databases, and the AP does achieve the ACID requirements demanded of any database system. Second the AP eliminates most of the program requirements of current systems. Among these MP problems are: Dynamic task scheduling, individual processor state assessment, processor task assignment, data broadcast and reduction, memory contention, bus arbitration software, multi-tasking and multi-thread software, processing for mutual exclusion, maintaining sequential consistency, data sorting and indexing, resorting/reindexing as data changes, data pointer management, shared resources, priority inversion, table/record/item data locking, lock management, coherency management (memory, cache) and preemption management. Each of these problems is the result of