Disjoint Paths Problem And Its Application In ATLAS Compiler System

In the past twenty years, the disjoint paths problem has become one of the key research topics that have been developing fast in the fields of computation theory and algorithm design. Research on the issue not only has strong theoretical significance, but also plays an important role in lots of practical applications. Along with the deepening of the research, the use will become more widespread. For instance, in high speed switch networks, it is necessary to construct node-disjoint paths for different pairs of nodes, which corresponding to isolated circuits. Another example, to dial a telephone number is essentially creating a communication link between the two terminals in telephone networks without conflict with others. Furthermore, disjoint paths problem also has important effects in VLSI design, scheduling, optical networks, and so forth.The construction of disjoint paths in a network is a basic issue in combinatorial optimization: given a network N=< V ,E>, and specified set T={< s i,t i>|1≤i≤k,? s i,t i∈V} of terminal pairs called connection requests, we are interested in finding disjoint paths for these requests. There are a number of classic NP-Complete problems that have no good approximation algorithm derived from the disjoint paths problem. Up to now, the lack of understanding of the disjoint paths problem is often an obstacle to good solutions of practical applications.The Abbreviated Test Language for All Systems (ATLAS) is an advanced test language which widely used in auto test system for avionics. ATLAS compiler system has to compile regular statements and allocates test devices for signal statements. It closely relates to construction of disjoint paths in switch networks to solve device allocation problem. Most of present systems often lower difficulty of device allocation by designing unblocking switch networks and allocate devices using simple greedy algorithms such as shortest path first algorithm.To better solve the device allocation problem encountered in the designing of the ATLAS compiler system, the present paper does a number of studies on the disjoint paths problem and introduces a fairly goodimplementation of ATLAS device allocation system using the results and algorithms achieved in this paper. To solve the device allocation problem of ATLAS, the present paper mainly focuses on two parts of research. First, it inspects the nature of the disjoint paths problem in several special kinds of graphs and then builds up a number of results and algorithms. Second, the present paper generalizes the disjoint paths problem and designs an algorithm for the problem in arbitrary graphs, which is used to solve the ATLAS device allocation problem.In the disjoint paths problem, the structure of graphs has crucial impact on the constructing of disjoint paths. In arbitrary graphs, the disjoint paths problem is very hard for little useful structural information in such graphs, while in some special kinds of graphs there are many properties which can be used for constructing disjoint paths. As far as the special properties of complete graphs and complete bipartite graphs are concerned, the present paper makes quantitative analysis of the impact after limiting the size of graph and set of connection requests. Then focusing on disjoint paths problem in split graphs and a special kind of graphs which have an induced graph in the form of complete bipartite graph, the present paper makes quantitative analysis of the impact too on the basis of the network flow theory and results we have got in complete graphs and complete bipartite graphs. Along with the results described above, we obtain several corresponding algorithms for disjoint paths problem in these special kinds of graphs.It is too harsh to restrict graph to any special kinds of graphs, so the significance of above research does not mean solutions for practical applications but techniques for designing switch networks. Our approach for designing unblocking networks has relatively simple process and imposes only a few restrictions on network structure. Currently it is being used to guide the design of switch networks in ATLAS compiler system.In addition to the previous researches on disjoint paths problem in some special kinds of graphs, the present paper designs a heuristic on-line algorithm for constructing disjoint paths in arbitrary graphs. With heuristic strategy for searching, the algorithm has an impressive performance on generic input though it has an exponential time complexity. The algorithm also can avoid nodes conflicts among connection requests by adjusting nodes used by each request during processing; moreover, it has nicer extensibilityand can be modified into an approximation algorithm. In basic disjoint paths problem, the connection request is just one pair of nodes in graph. Taking time into consideration, this paper generalizes the disjoint paths problem into a new model, which modeling the device allocation of ATLAS well. This generalization can be handled by the previous algorithm after a little modification.To apply the algorithm presented in paper to the device allocation of ATLAS, it is necessary to describe the device allocation problem with the disjoint paths problem in arbitrary graphs. Device allocation is a practical problem in a real system, so there are many details which have no counterparts even in the generalization of the disjoint paths problem. Though the device allocation can be modeled well by the disjoint paths problem, we have to handle all these details in device allocation. In chapter five, this paper models the device allocation problem and build up the device allocation subsystem of ATLAS, then, presents carefully how to handle all the details of device allocation. The present paper also compares performance of this implementation of ATLAS device allocation system with several others developed before. The contrast of the statistics shows that our algorithm has best performance and works alright in ATLAS compiler system.Finally, the present paper summarizes the works we have done and discusses the way for future researches. For the sake of solving the device allocation of ATLAS better, the paper discusses a number of directions for further researches, and along these lines there are primary research methods. All of them provide the foundation for future work.