Details:

Creators:
Mangharam, Rahul
Corporate Creators:
University of Pennsylvania. Dept. of Systems Engineering
Corporate Contributors:
University Transportation Centers Program (U.S.)
Subject/TRT Terms:
[+]
Algorithms Computation Time GPUs Graphics Processing Units Highways Real Time Data Processing Research Hub Traffic Models Traffic Simulation Vehicle Traffic Simulator
Resource Type:
Tech Report
Geographical Coverage:
United States
TRIS Online Accession Number:
01675039
Edition:
Final Report
Corporate Publisher:
University Transportation Centers Program (U.S.)
Abstract:
Most algorithms are run-to-completion and provide one answer upon completion and no answer if interrupted before completion. On the other hand, anytime algorithms have a monotonic increasing utility with the length of execution time. This investigation focuses on the development of time-bounded anytime algorithms on Graphics Processing Units (GPUs) to trade-off the quality of output with execution time. Given a time-varying workload, the algorithm continually measures its progress and the remaining contract time to decide its execution pathway and select system resources required to maximize the quality of the result. To exploit the quality-time trade-off, the focus is on the construction, instrumentation, on-line measurement and decision making of algorithms capable of efficiently managing GPU resources. The author demonstrates this with a Parallel A* routing algorithm on a CUDA-enabled GPU. The algorithm execution time and resource usage is described in terms of CUDA kernels constructed at design-time. At runtime, the algorithm selects a subset of kernels and composes them to maximize the quality for the remaining contract time. The author demonstrates the feedback-control between the GPU-CPU to achieve controllable computation tardiness by throttling request admissions and the processing precision. As a case study, the author has implemented AutoMatrix, a GPU-based vehicle traffic simulator for real-time congestion management which scales up to 16 million vehicles on a US street map. This is an early effort to enable imprecise and approximate real-time computation on parallel architectures for stream-based time-bounded applications such as traffic congestion prediction and route allocation for large transportation networks.
Format:
PDF
Funding:
DTRT12GUTC11
Collection(s):
US Transportation Collection University Transportation Centers
Main Document Checksum:
[+]
urn:sha256:079425424563c09cc0706117f066837f6c5b1639be7d9086fcbb93bded1847e4
Download URL:
https://rosap.ntl.bts.gov/view/dot/36246/dot_36246_DS1.pdf
File Type:

Supporting Files

• No Additional Files

More +