Large scale parallel state space search utilizing graphics processing units and solid state disks

摘要

The evolution of science is a double-track process composed of theoretical insights onthe one hand and practical inventions on the other one. While in most cases new theoretical insights motivate hardware developers to produce systems following the theory,in some cases the shown hardware solutions force theoretical research to forecast theresults to expect.Progress in computer science rely on two aspects, processing information and storing it. Improving one side without touching the other will evidently impose new problemswithout producing a real alternative solution to the problem. While decreasingthe time to solve a challenge may provide a solution to long term problems it will failin solving problems which require much storage. In contrast, increasing the availableamount of space for information storage will definitively allow harder problems to besolved by offering enough time.This work studies two recent developments in the hardware to utilize them in thedomain of graph searching. The trend to discontinue information storage on magneticdisks and use electronic media instead and the tendency to parallelize the computationto speed up information processing are analyzed.Storing information on rotating magnetic disk has become the standard way sincea couple of years and has reached a point where the storage capacity can be seen asinfinite due to the possibility of adding new drives instantly with low costs. However,while the possible storage capacity increases every year, the transferring speed doesnot. At the beginning of this work, solid state media appeared on the market, slowlysuppressing hard disks in speed demanding applications. Today, when finishing thiswork solid state drives are replacing magnetic disks in mobile computing, and computingcenters use them as caching media to increase information retrieving speed.The reason is the huge advantage in random access where the speed does not drop sosignificantly as with magnetic drives.While storing and retrieving huge amounts of information is one side of the medal,the other one is the processing speed. Here the trend from increasing the clock frequencyof single processors stagnated in 2006 and the manufacturers started to combinemultiple cores in one processor. While a CPU is a general purpose processor themanufacturers of graphics processing units (GPUs) encounter the challenge to performthe same computation for a large number of image points. Here, a parallelization offershuge advantages, so modern graphics cards have evolved to highly parallel computinginstances with several hundreds of cores. The challenge is to utilize these processorsin other domains than graphics processing.One of the vastly used tasks in computer science is search. Not only disciplines withan obvious search but also in software testing searching a graph is the crucial aspect.Strategies which enable to examine larger graphs, be it by reducing the number ofconsidered nodes or by increasing the searching speed, have to be developed to battlethe rising challenges. This work enhances searching in multiple scientific domainslike explicit state Model Checking, Action Planning, Game Solving and ProbabilisticModel Checking proposing strategies to find solutions for the search problems.Providing an universal search strategy which can be used in all environments toutilize solid state media and graphics processing units is not possible due to the heterogeneous aspects of the domains. Thus, this work presents a tool kit of strategies tiedtogether in an universal three stage strategy. In the first stage the edges leaving a nodeare determined, in the second stage the algorithm follows the edges to generate nodes.The duplicate detection in stage three compares all newly generated nodes to existingonce and avoids multiple expansions.For each stage at least two strategies are proposed and decision hints are given tosimplify the selection of the proper strategy. After describing the strategies the kit isevaluated in four domains explaining the choice for the strategy, evaluating its outcomeand giving future clues on the topic.