Wu, Jie

We propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 2-dimensional mesh (2-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 2-D mesh is partitioned into four submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. These algorithms are extended to a 3-dimensional mesh (3-D mesh), and are generalized to a d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations.

In this thesis, a low interprocessor communication overhead and high performance data parallelism parallel application model in a network of workstations (NOWs) is proposed. Checkpointing and rollback technologies are used in this model for performance enhancement purpose. The proposed model is analyzed both theoretically and numerically. The simulation results show that a high performance of the parallel application model is expected. As a case study, the proposed model is used to the parallel Everglades Landscape Fire Model (ELFM) code which was developed by South Florida Water Management District (SFWMD). The parallel programming environment is Message-Passing Interface (MPI). A synchronous checkpointing and rollback mechanism is used to handle the spread of fire which is a dynamic and irregular component of the model. Results show that the performance of the parallel ELFM using MPI is significantly enhanced by the application of checkpointing and rollback.

To improve the performance of parallel/distributed systems, we propose four parallel load balance algorithms. The new partition algorithm achieves load balance among processors via domain partition. If we assume the problem domain is evenly load distributed, this algorithm will divide the whole domain into a required number of subdomains with the same area. If a problem domain has a dynamic load distribution, although the new partition algorithm is still suitable for the initial mapping, we propose three dynamic load balance algorithms. These dynamic algorithms achieve load balance among processors by transferring load among processors. We applied the new partition algorithm to a specific domain and compared the method to some existing partition algorithms. We also simulated three dynamic load balance algorithms. Results of comparisons and simulations show that all the four algorithms have satisfactory performance.

In this thesis, we measure and analyze the effects of compression in a demand paging operating system. We first explore existing compression algorithms and page replacement policies currently in use. Then we examine the OS/2 operating system which is modified to include page-based compression. Software trace hooks are inserted into the operating system to determine the amount of time required to process a page fault for each type of page, e.g. non-compressed, compressed, zero-filled, and the number of page faults for each type of page. Software trace measurements as well as physical timings are taken on a system without compressed pages and the same system with compressed pages. We find the system with compressed pages shows a slight increase in paging activity for memory constrained systems, but performance (time) is improved in both memory constrained and unconstrained systems.

We study the embedding of binomial trees with variable roots in faulty hypercubes. Based on novel embedding strategies, we propose three embedding algorithms with variable nodes as the root. The first algorithm can tolerate up to n - 1 faulty links, but the execution can be done within log2(n - 1) subcube splits. The second one can tolerate up to [(3(n - 1))\2] faulty links. The last one can tolerate up to [(3(n - 4))\2] faulty nodes.

We propose the enhanced Fibonacci cube (EFC), which is defined based on the sequence Fn = 2(n-2) + 2F(n-4). We study its topological properties, embeddings, applications, routings, VLSI/WSI implementations, and its extensions. Our results show that EFC retains many properties of the hypercube. It contains the Fibonacci cube (FC) and extended Fibonacci cube of the same order as subgraphs and maintains virtually all the desirable properties of FC. EFC is even better in some structural properties, embeddings, applications and VLSI designs than FC or hypercube. With EFC, there are more cubes with various structures and sizes for selection, and more backup cubes into which faulty hypercubes can be reconfigured, which alleviates the size limitation of the hypercube and results in a higher level of fault tolerance.

In this thesis work, techniques developed in the science of genetic computing is applied to solve the problem of planning a robot calibration experiment. Robot calibration is a process by the robot accuracy is enhanced through modification of its control software. The selection of robot measurement configurations is an important element in successfully completing a robot calibration experiment. A classical genetic algorithm is first customized for a type of robot measurement configuration selection problem in which the robot workspace constraints are defined in terms of robot joint limits. The genetic parameters are tuned in a systematic way to greatly enhance the performance of the algorithm. A recruit-oriented genetic algorithm is then proposed, together with new genetic operators. Examples are also given to illustrate the concepts of this new genetic algorithm. This new algorithm is aimed at solving another type of configuration selection problem, in which not all points in the robot workspace are measurable by an external measuring device. Extensive simulation studies are conducted for both classical and recruit-oriented genetic algorithms, to examine the effectiveness of these algorithms.

The utilization of a multiprocessor system is enhanced when idle time of processors is reduced. Allocation of processes from overloaded processors to idle processors can balance the load on multiprocessor systems and increase system throughput by reducing the process execution time. This thesis presents a study of parameters, issues and existing algorithms related to load balancing. The performance of load balancing on hypercubes using three new algorithms is explored and analyzed. A new algorithm to balance load on hypercubes in the presence of link faults is presented and analyzed here. Another algorithm to balance load on hypercube systems containing faulty processors is proposed and studied. The applicability of load balancing to real life problems is demonstrated by showing that the execution of branch and bound problem on hypercubes speeds up when load balancing is used.

Interprocessor communication plays an important role in the performance of multicomputer systems, such as hypercube multicomputers. In this thesis, we consider the multicast problem for a hypercube system in the presence of faulty components. Two types of algorithms are proposed. Type 1 algorithms, which are developed based on local network information, can tolerate both node failures and link failures. Type 2 algorithms, which are developed based on limited global network information, ensure that each destination receives message through the shortest path. Simulation results show that type 2 algorithms achieve very good results on both time and traffic steps, two main criteria in measuring the performance of interprocessor communication.

When there are a large number and a variety of users in a system, the authorization rules for these users will become too difficult and cumbersome to maintain and the evaluation algorithm would not be efficient. Also, it is hard for security administrators to understand why a specific user is given a set of rights. In this thesis we develop group structures to solve these problems. Groups of users rather than individual users are subjects that receive access rights from the authorization system. We present structurings and primitives for user groups. Although they are presented in the context of an object-oriented database system they are general and could be applied to other data model, and even in operating systems.