Thesis (Ph. D.)--University of Wisconsin--Madison, 1983. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 94-95).

by Hoi Wing, Yung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 56-60). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Literature Review --- p.3 / Chapter 1.2.1 --- On the Fixed Multiprocessor Job Scheduling Problems --- p.6 / Chapter 1.2.2 --- On the Nonfixed Multiprocessor Job Scheduling Problems --- p.8 / Chapter 1.3 --- Problem Formulation --- p.12 / Chapter 1.4 --- Organization of the Thesis --- p.13 / Chapter 2 --- Genetic Algorithms --- p.15 / Chapter 2.1 --- Basic Concepts --- p.15 / Chapter 2.2 --- Main components --- p.17 / Chapter 3 --- A New Genetic Algorithm --- p.24 / Chapter 3.1 --- Coding --- p.25 / Chapter 3.1.1 --- Simple Example --- p.28 / Chapter 3.2 --- Similarity of Chromosomes --- p.30 / Chapter 3.3 --- Fitness Evaluation --- p.33 / Chapter 3.4 --- Configurations --- p.35 / Chapter 3.4.1 --- Parent Selection --- p.35 / Chapter 3.4.2 --- Multipoint Crossover --- p.36 / Chapter 3.4.3 --- Multipoint Mutation --- p.38 / Chapter 3.4.4 --- Replacement Step --- p.38 / Chapter 3.4.5 --- Termination Criterion --- p.39 / Chapter 4 --- Experimental Results --- p.41 / Chapter 4.1 --- Total Weighted Completion Time --- p.41 / Chapter 4.1.1 --- Lee and Cai's Algorithm --- p.42 / Chapter 4.1.2 --- Computational Results --- p.44 / Chapter 4.1.3 --- On the Problem of Minimizing the Total Completion Time --- p.46 / Chapter 4.2 --- Makespan --- p.48 / Chapter 4.2.1 --- Mahesh's Algorithms and Linn & Chen's Algorithm --- p.48 / Chapter 4.2.2 --- Computational Results --- p.52 / Chapter 5 --- Conclusion --- p.54 / Bibliography --- p.56

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 119-122. / by Thomas Lee Anderson. / M.S.

"Grand Challenge" problems such as climate modeling to predict droughts and human genome mapping to predict and possibly cure diseases such as cancer require massive computing power. Three kinds of computer systems currently used in attempts to solve these problems are "Big Iron" multicomputers such as the Intel Paragon, workstation cluster multicomputers, and distributed shared memory multiprocessors such as the Cray T3D. Machines such as these are inefficient in executing some or all of a set of global program operations which are important in many of the "Grand Challenge" programs. These operations include synchronization, reduction, MAX, MIN, one-to-all broadcasting, all-to-all broadcasting, and orderly access to global shared variables. My hypothesis was that a secondary network with a wide tree topology and one or more centralized processors optimized for these operations could substantially decrease their execution time on all three types of systems. To test my hypothesis, I developed the secondary network and Coordination Processor(COP) system described in this dissertation, modeled the major blocks of the design in VHDL, and simulated these blocks to verify their logic and get realistic timing values. The analyses developed for the COP system clearly demonstrate that it can speed up a variety of common global operations by as much as 2-3 orders of magnitude when added to any of several current multicomputers and multiprocessors. Examples show that this speedup reduces overall execution time for important scientific programs and computational kernels by an average of 25% at an increase in system cost of only about 2%. Further analyses show that for these global operations the COP system has a greater combination of speed and versatility than any other system.

Workstation cluster multicomputers are increasingly being applied for solving scientific problems that require massive computing power. Parallel Virtual Machine (PVM) is a popular message-passing model used to program these clusters. One of the major performance limiting factors for cluster multicomputers is their inefficiency in performing parallel program operations involving collective communications. These operations include synchronization, global reduction, broadcast/multicast operations and orderly access to shared global variables. Hall has demonstrated that a .secondary network with wide tree topology and centralized coordination processors (COP) could improve the performance of global operations on a variety of distributed architectures [Hall94a]. My hypothesis was that the efficiency of many PVM applications on workstation clusters could be significantly improved by utilizing a COP system for collective communication operations. To test my hypothesis, I interfaced COP system with PVM. The interface software includes a virtual memory-mapped secondary network interface driver, and a function library which allows to use COP system in place of PVM function calls in application programs. My implementation makes it possible to easily port any existing PVM applications to perform fast global operations using the COP system. To evaluate the performance improvements of using a COP system, I measured cost of various PVM global functions, derived the cost of equivalent COP library global functions, and compared the results. To analyze the cost of global operations on overall execution time of applications, I instrumented a complex molecular dynamics PVM application and performed measurements. The measurements were performed for a sample cluster size of 5 and for message sizes up to 16 kilobytes. The comparison of PVM and COP system global operation performance clearly demonstrates that the COP system can speed up a variety of global operations involving small-to-medium sized messages by factors of 5-25. Analysis of the example application for a sample cluster size of 5 show that speedup provided by my global function libraries and the COP system reduces overall execution time for this and similar applications by above 1.5 times. Additionally, the performance improvement seen by applications increases as the cluster size increases, thus providing a scalable solution for performing global operations.

A method to parallelize external sorts on a shared memory multiprocessing system is presented in this thesis. The main goal of the thesis is to develop a sorting package that is scale able and efficient. No prior knowledge of the nature, source or size of the data is assumed for this work. A dynamic load-balancing architecture is used with no static allocation of tasks to processes. The package consists of an interface and a kernel. The interface provides the sort with the following - the sort input, output and temporary work spaces as abstract data types (ADTs), memory available, number of processes available, compare routine to compare records, etc. Only the interface needs to be changed to suit different environments. The kernel implements the parallel sort algorithm. The traditional sort merge technique is used for the external sort as opposed to a distributive sorting technique. Memory-sized runs are first generated and later merged. Parallel binary merges is the technique used for both the run generation and the merge phase. A forecasting table is used to read ahead in the merge phase.

M.S. / Computer Science & Engineering / Programming in a multiprocessing environment creates additional complexity issues above those encountered in a uniprocessing model. Animation of the underlying software data structures has been shown to help in management of such issues in uniprocessing environments. Animation tools for multiprocessing environments should also be of assistance to software engineers constructing parallel processing software systems. MPA is an environment that supports creation ofanimations that support multiprocessing applications in the Smalltalk programming environment.

System-on-a-chip (SoC) designs is characterized by heavy reuse of IP blocks to satisfy specific computing needs for target applications, reduce overall design cost, and expedite time-to-market. To meet their performance goal and cost constraint, SoC designers integrate multiple, sometimes heterogeneous, processor IPs to perform particular functions. This design approach is called Multiprocessor SoC (MPSoC). In this thesis, I investigated generic methodologies for enabling efficient communication among heterogeneous processors and quantified the efficiency of coherence traffic. Hardware techniques for two main MPSoC architectures were studied: Integration of cache coherence protocols for shared-bus-based MPSoCs and Cache coherence support for non-shared-bus-based MPSoCs. In the shared-bus-based MPSoCs, the integration techniques guarantee data consistency among incompatible coherence protocols. An integrated protocol will contain common states from these coherence protocols. A snoop-hit buffer and region-based cache coherence were also proposed to further enhance the coherence performance. For the non-shared-bus-based MPSoCs, bypass and bookkeeping approaches were proposed to maintain coherence in a new cache coherence-enforced memory controller. The simulations based on micro-benchmark and RTOS kernel showed the benefits of my methodologies over a generic software solution. This thesis also evaluated and quantified the efficiency of coherence traffic based on a novel emulation platform using FPGA. The proposed technique can completely isolate the intrinsic delay of the coherence traffic to demonstrate the impact of coherence traffic on system performance. Unlike previous evaluation methods, this technique eliminated non-deterministic factors in measurements such as bus arbitration delay and stall in the pipelined bus. The experimental results showed that the cache-to-cache transfer in the Intel server system is less efficient than the main memory access.

No description available.

No description available.