Research And Application Of Distributed Parallel Algorithm On Traffic Simulation

With the accelerating development of the market and economy, thetransportation becomes very busy and the number of various vehiclesincreases very quickly, which makes the traffic demand increase promptlyand the traffic facilities lag behind the demand. The contradiction betweenthe complex composition of traffic flow and backward methods of trafficcontrol is becomingmoreandmoreoutstanding. Abovetwoaspects interactwith each other and lead to serious traffic jam and immeasurable negativesocialinfluence.Trafficjamhasbecomethe'bottleneck'inthedevelopmentofeconomyandsocietytosomeextent.It is not themosteffectivewaytosettlethequestionoftrafficjam onlyby increasing the road area or the road length simply. The other keyquestion is to take the scientific organization and management measure tomake full use of the existing traffic network and make the traffic flow ingood order to the furthest extent. This needs to make deep research of thetrafficcharacteristics.Computersimulationisoneofthemosteconomicandeffectivewaystodosuchresearch.Asaresult,developinganewgenerationofmicroscopictrafficsimulationmodelhasbecomeanurgentandimportanttaskforscienceandtechnologyofourcountry.Microscopic traffic network simulation describes each vehicle entities'movements.Whenthescaleoftrafficnetworkbecomeslarger,thespeedsoftraffic network will slow down and simulation computing also needs muchtime and resources. Temporally, it is hard to achieve computation with asingle CPU. Because of the mainframe computer's large price, it is not easyto popularize widely. However, the distributed cluster has such traits:autonomy, parallel, expansibility, modularity and low cost etc. And it alsoacceleratessimulationspeedsandcomputationalefficiency.Consequently,it isaneffectivemeasuretoenhancesimulationspeedsandefficiency,managetraffic congestion and control reality in traffic network simulation with thedistributedparallelcomputingmethods.According to parallel characteristics of traffic network simulation andweak relativity of differert simulation area computing, domaindecomposition method, which divides computational loads into someapproximately equal parts, is used in traffic network. An individual PC ofthe cluster system processes each part. At last, the total simulation resultsare generated. In simulation process, parallel program uses master-slavearchitecture to equally allocate computational load to each processor ofcluster system. The master process controls general scheduling and slaveprocess is reasonpasible for the computatiton of each childnetwork. Inparallel trafficnetworksimulation,tokeeploadbalancingofeachprocessorand minimize communication spending network-partition is a veryimportantstep.Accordingtonetwork-topalogyarchitectures,trafficnetworkis decomposed into several sub-networks of similar size. And eachprocessor of parallel computer carries out simulation procedure for one ofthese sub-networks, which exchanges vehicle information among thesesub-networkstocompleteparallelsimulationofentiretrafficnetwork.Study on distributed and parallel simulation is a rapidly developingresearch area of international simulation field. This article researchesparallel characteristics, constructs parallel simulation data structure oftrafficnetworkandbuilds trafficsimulationplatform basedonMPI/OOMPIparallel computational library. Intersections are viewed as basic parallelsimulation unit. Metis program library is used to cut the large trafficnetwork into the approximately equal several parts, which are processedwith each processor. This effectively transfers the loads to each slaveprocess.Thespeedandefficiencyofparallelsimulationareimproved.Parallel simulation performances mostly are evaluated by computational complexity, including time complexity and dimensionalcomplexity. The goal of parallel simulation decreases time as possible.Generallyit is implemented byincreasingthe dimensional complexity, suchas dimensions and number of processors. Parallel simulation programcomplexity has great difference with sequential program. It has manyfactors need to be considerable, such as workload, execution time, numberofprocessors,speed-up,efficiency,extensibilityandgranularityetc.At last this article mostly describes parallel algorithm efficiency fromthe following four aspects, which include execution time, speed-up,efficiencyand extensibility, in 5 different traffic networks at 1-8 processors.And it is concluded that when the traffic network is small, there is a mostoptimized number of nodes machine to get the greatest efficiency.Temporally, the parallel computing efficiency is more worthy than timespent in communication and synchronization. When the traffic network islarge, the much efficiency, speed-up can be got. The thick granularitypartition is more proper for parallel microscopic traffic simulation. Whenthe traffic network is large, we can get more parallel efficiency, speed-upandextensibility.