Search

A shared-memory multiprocessor has various inherent or potential hardware and software bottlenecks. The software bottleneck is mainly due to the synchronization of processes and the access of critical sections. The most frequently occurred software bottleneck, the monitor bottleneck, which is caused by the scheduling of large number of processors, is investigated. The monitor bottleneck is created due to the mutually exclusive access of the single scheduling monitor. Monitor bottleneck can be resolved using multiple monitors. However, multiple monitors may result in a low processor utilization due to load imbalancing. This paper studies the tradeoffs in designing an efficient process scheduling strategy. [ABSTRACT FROM AUTHOR]

It is desirable for the load in a distributed system to be balanced evenly. A dynamic process migration protocol is needed in order to achieve load balancing in a user transparent manner. A distributed algorithm for load balancing which is network topology independent is proposed in this paper. Different network topologies and low-level communications protocols affect the choice of only some system design parameters. The "drafting" algorithm attempts to compromise two contradictory goals: maximize the processor utilization and minimize the communication overhead. The main objective of this paper is to describe the dynamic process migration protocol based on the proposed drafting algorithm. A sample distributed system is used to further illustrate the drafting algorithm and to show how to define system design parameters. The system performance is measured by simulation experiments based on the sample system. [ABSTRACT FROM AUTHOR]

A loosely coupled multiprocessor system contains multiple processors which have their own local memories. To balance the load among multiple processors is of fundamental importance in enhancing the performance of such a multiple processor system. Probabilistic load balancing in a heterogeneous multiple processor system with many job classes is considered in this study. The load balancing scheme is formulated as a nonlinear programming problem with linear constraints. An optimal probabilistic load balancing algorithm is proposed to solve this nonlinear programming problem. The proposed load balancing method is proven globally optimum in the sense that it results in a minimum overall average job response time on a probabilistic basis. [ABSTRACT FROM AUTHOR]

This paper presents a Markov chain model to analyze the performance of shared-resource array processors for multiple vector processing. Such a parallel processor contains multiple control units sharing a resource pool of processing elements and operating with multiple single-instruction multiple-data streams (MSIMD). In the steady state, the Markov model corresponds to a two-dimensional Markov chain, which can be expressed by a set of equilibrium equations. An iterative method is developed to solve the Markov chain after projecting the equilibrium equations onto a one-dimensional state space. The convergence rate of the iterative method can be greatly enhanced by choosing starting values corresponding to the approximated analytical results obtained earlier by the authors. [ABSTRACT FROM AUTHOR]

Presents a correction to the article "Optimal Load Balancing in a Multiple Processor System with Many Job Classes," by Lionel M. Ni and Kai Hwang in the May 1985 issue, with regards to the Load Balancing Algorithm.

The ability to quickly determine how to derive a given query from a set of prestored fragments is highly demanded in many database applications, especially in distributed database systems, where the communication cost is a major concern. The main difficulty in solving this problem lies in the implication problem-given two predicates σQ and σT, can σQ imply σT(σQ → σT? The implication problem has been solved by converting it into a satisfiability problem. No detailed study of the implication problem on its own has been presented. In this paper, we study the general implication problem in which all six comparison operators: =, ≠, <, >, ≤, >, as well as conjunctions and disjunctions are allowed. We proved that the general implication problem is NP-hard. In the case when "≠" operators are not allowed in σQ and disjunctions are not allowed in σQ a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the "≠" operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the "≠" operator or disjunctions in the predicates. Necessary conditions for detecting when the "≠" operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods. [ABSTRACT FROM AUTHOR]