TOPOLOGY INDEPENDENT NETWORK SOLUTION TO LARGE LINEAR SYSTEMS

Abstract

The recent development of high speed networks and fast processors has made distributed computing on multicomputer environments a good alternative to parallel processing on a multiprocessor system. The former has been more severely limited in bandwidth than the latter, but this is changing dramatically. It may be anticipated that only latency and shared usage will distinguish the two classes of machines. We want to solve large scale linear systems efficiently in a multicomputer environment - a cluster of workstations. Linear system solving is chosen as the main focus because of its importance from both practical and theoretical viewpoints. The first issue we encountered is to have a good general computational model to abstract the real network system. Since there is no consensus on the type of interconnection network to be used in parallel or distributed systems, it is therefore useful to examine a paradigm that insists on not knowing the interconnection topology. We used such a topology independent model which is variously labeled as LogP or Postal model. Previous work on the LogP model has placed emphasis on its use as a model for efficient broadcasting. We extend its role to designing and analyzing distributed algorithms through investigation on the relationship between the model and the performance metric that is expressed in terms of efficiency and inverted bandwidth. We formulate the bandwidth requirement of the network system as a function of the number of processors, problem size, processor speed and efficiency. Efficiency is more meaningful than speedup in distributed network computing since the workstations do not work solely on the cooperative tasks most of the time. Using the iso-efficiency graph derived from the relationship, we are able to tell the scale of parallelism. In the LogP model setting, we design efficient algorithms to solve large linear systems. We first consider the solving of dense linear systems using direct techniques. We analyze and compare the different schemes for data partitioning before investigating the effect of pivoting on the distributed algorithms. Experiments have been used to provide deeper insight into algorithmic mechanisms and guide the analytical results. To solve sparse linear systems, iterative techniques are usually used. We investigate the performance of the different techniques on network systems using experimental approaches. The iterative techniques considered include classical techniques such as Jacobi and SOR methods, and newer methods like Conjugate-Gradients. We also implemented a wavelet based multilevel preconditioning iterative solver. The usefulness of the LogP model is clearly not restricted to solving linear systems. We have designed efficient algorithms for other numerical and general computer science problems. The theoretical analysis of these algorithms generally matched the results obtained from numerical experiments. In the course of our research, we have developed a numerical library that is fairly complete and meant for distributed network computing. We are currently using this library to develop a software simulator for catheter navigation in interventional radiology operations.