 |
 |
 |
 |
| |
|||||
|
|
|
MITRE has recently developed a fast-time simulation tool capable of computing congestion-related delays. The tool, called the Detailed Policy Assessment Tool (DPAT), is built on a parallel discrete-event simulation engine, which uses optimistic computing technology to achieve ultra-fast run times. DPAT is able to compute the delays for about 400,000 air traffic control operations (takeoff, landing, or sector handoff) in less than one minute on a four-processor, 300 Mhz Sun SPARC workstation. Such quick run times allow different uses for DPAT: as a fast assessment capability for quick turnaround studies, as an engine to investigate hundreds or thousands of parametric variations for more comprehensive sensitivity studies, or as a decision support tool for real-time aviation decisions. At the heart of DPAT is its optimistic parallel discrete-event simulation engine, called Georgia Tech Time Warp (GTW), based upon parallel computing technology, which has recently found widespread use throughout the simulation community. Optimistic simulation works as follows. Simulations are decomposed into hundreds or thousands of entities that schedule events for each other and control the passage of simulation time. For example, in the simulation of air traffic there are entities that represent airports and en route airspace sectors, and events that correspond to arrival and departure of planes at airports and transfer of airplanes between air traffic sectors. Conceptually, such a simulation contains much parallelism. The real world, for example, often contains much simultaneous activity, such as the arrival and departure of airplanes at different airports, which would appear to lead to natural parallel computation, which can cause large increases in execution speed. However, the pursuit of parallel simulation eluded researchers for many years. The chief problem is simulation time, a global variable throughout all the entities that must properly be coordinated. As entities are distributed among processors, optimistic simulation technology allows each entity to keep track of its own local simulation time. In effect, each entity has its own simulation clock. It processes events from its local event list in strict simulation time order, changing its state and posting events for other entities as appropriate. As each entity performs these tasks separately and in parallel on different processors, occasionally one entity's clock will run slower than another's (perhaps it had more computation for each event, perhaps there were more events scheduled for it); but for whatever reason, the time kept by simulation clocks can drift. Such drifting is harmless until an entity with an early simulation clock posts an event for a second entity, where the time of the scheduled event is earlier in simulation time than the second entity's current local clock value. Such a situation is often called a "time fault" (like a virtual memory system's page fault) and requires some type of synchronization to handle the case. Parallel simulation researchers have devised clever techniques to handle such cases, relying on rollback and message cancellation. "Rollback" is resetting the second entity's simulation clock back so that it can correctly process the late straggler message from the slower first entity. "Message cancellation" is the technique used to nullify any events that the second entity posted before the arrival of the straggler message. Parallel simulation techniques trade off the amount of information that must be saved with the amount of optimistic processing that is actually allowed. Some methods throttle the execution of entities to prevent their local clocks from drifting too far ahead of the rest of the entities, which limits the amount of extracted parallelism for less overhead in rollbacks and message cancellations. Other methods allow unlimited execution of entities without barriers, thereby maximizing extracted parallelism but possibly causing higher rollback and message cancellation costs. Still other methods try to find a balance between throttling and fully optimistic execution. The GTW system, upon which DPAT is based, throttles execution through a memory-based scheme that allows an entity to process as fast as possible until the memory buffer allocated to its event list is full. At that point, execution stops until memory is freed up. Memory reclamation occurs as the time of the earliest entity in the simulation increases (called, the "Global Virtual Time," or GVT). Events and state earlier than GVT can be deleted (because there is no reason to roll back earlier than GVT), which frees up memory for further execution. In addition to the memory-based throttling scheme, which works well, GTW is optimized for performance on shared memory workstations (although it will also run in a distributed memory environment). It relies on multithreaded technology to provide the parallel processes, and its computation of GVT, as well as message passing among entities, all utilize shared memory optimizations. As a result, GTW is one of the fastest simulation engines available for parallel processing today. Besides parallel simulation technology, DPAT includes several other unique advances that make it stand out in the world of air traffic control modeling. DPAT interfaces to the Web through Common Gateway Interface (CGI) scripts. Its Web-based interface allows aviation analysts (who are not trained computer science experts) to run the parallel simulation from their local desktops using either Netscape or Internet Explorer. The Web interface provides capabilities to set up the input for a run, run the model, and then graph the output, view the raw results, and save the data to a local file. The runs may be stored for future retrieval, and two or more may be compared side by side for analysis purposes. DPAT has also been flexibly coded so that most of the important information (airports, traffic routes, airplane performance, enroute sectors) is provided through text-based data files. This has allowed MITRE to configure DPAT for air traffic analysis not only in the Continental United States (CONUS), but also in Asia, Canada, Latin America, and Taiwan. DPAT, however, is much more than an interesting example of the use of parallel simulation and other advanced computing technologies. DPAT is a world-class analysis engine in its own right. Among its dozens of uses have been the benefit assessment of new procedures allowing more planes to land in poor weather conditions, the assessment of future air travel on the Asian continent, the performance assessment of CONUS air travel given FAA projections of future traffic demand and infrastructure improvements, and the determination of whether infrastructure improvement plans will meet their performance goals. DPAT is currently being tested for use with real-time planners at the FAA's Air Traffic Control System Command Center. While the demand for air travel continues to grow, and congestion and delay become problems not only within the United States but throughout the world, the need for the type of rapid air traffic simulation provided by DPAT will also grow. By combining several computer science technologies, DPAT is able to help aviation planners assess the results of their efforts and plan more effectively for future growth. For more information, please contact Frederick Wieland using the employee directory. |
Solutions That Make a Difference.® |
|
|
Congestion and delay are common attributes of modern transportation
systems. In its Long Range Forecasts, the Federal Aviation Administration
(FAA) has projected a 50% growth in commercial aircraft operations between
now and the year 2020. The current yearly operating costs incurred by
commercial air carriers due to air traffic delays are about $3 billion,
and that number excludes the indirect costs of delays to the aviation
users. If unmet by infrastructure improvements, the projected future
demand will exacerbate current flight delays and escalate the direct
and indirect costs of these delays.