Numerical studies of flow around aircraft using the multiprocessor computer systems

The topical problems of the computational aerodynamics were described. Consideration was given to the realization of algorithms on the multiprocessor computer systems. Difficulties arising with such problems were described. Examples of numerical modeling of some problems were presented.     

Fault-tolerant expansion of system area networks in multiprocessor computer systems

A method for constructing a fault-tolerant system area network in the form of a flat network consisting of several copies of the original network is proposed. The flat network is constructed according to the theory of incomplete balanced block designs.     

Probabilistic models of computer systems

Summary In this paper we examine certain problems related to the use of diffusion approximations for the approximate modelling of computer systems. In particular we develop a model which allows us to handle waiting times and batch arrivals: these results are a new approach to the use of diffusion approximations. We also examine the effect of the distribution of holding times at boundaries: this question had remained open in earlier studies. We show that the stationary distributions associated with these diffusion models depend only on the average residence time of the process on the boundaries and not on the complete distribution function. This result justifies the use of exponential holding times as had been done in an earlier study.     

An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems

Scheduling precedence constrained task graphs, with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication heuristics are more effective, in general, for fine grain task graphs and for networks with high communication latencies. However, most of the available duplication algorithms are designed under the assumption of unbounded availability of fully connected processors, and lie in a high complexity range. Low complexity optimal duplication algorithms work under restricted cost and/or shape parameters for the task graphs. Further, the required number of processors grows in proportion to the task-graph size significantly. An improved duplication strategy is proposed that works for arbitrary task graphs, with a limited number of interconnection-constrained processors. Unlike most other algorithms that replicate all possible parents/ancestors of a given task, the proposed algorithm tends to avoid redundant duplications and duplicates the nodes selectively, only if it helps in improving the performance. This results in lower duplications and also lower time and space complexity. Simulation results are presented for clique and an interconnection-constrained network topology with random and regular benchmark task graph suites, representing a variety of parallel numerical applications. Performance, in terms of normalized schedule length and efficiency, is compared with some of the well-known and recently proposed algorithms. The suggested algorithm turns out to be most efficient, as it generates better or comparable schedules with remarkably less processor consumption.     

Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems

Scheduling program tasks on processors is at the core of the efficient use of multiprocessor systems. Most task-scheduling problems are known to be NP-Hard and, thus, heuristics are the method of choice in all but the simplest cases. The utilization of acknowledged sets of benchmark-problem instances is essential for the correct comparison and analysis of heuristics. Yet, such sets are not available for several important classes of scheduling problems, including multiprocessor scheduling problem with communication delays (MSPCD) where one is interested in scheduling dependent tasks onto homogeneous multiprocessor systems, with processors connected in an arbitrary way, while explicitly accounting for the time required to transfer data between tasks allocated to different processors. We propose test-problem instances for the MSPCD that are representative in terms of number of processors, type of multiprocessor architecture, number of tasks to be scheduled, and task graph characteristics (task execution times, communication costs, and density of dependencies between tasks). Moreover, we define our task-graph generators in a way appropriate to ensure that the corresponding problem instances obey the theoretical principles recently proposed in the literature.     

Constructing a family of algorithmic languages for programming and design of multiprocessor computer systems

Conclusion The paper describes approaches to building a family of compatible algorithmic languages for design of circuitry and programming software for multiprocessor systems under development at the Institute of Cybercsics of the Academy of Sciences of the Ukrainian SSR. Several members of the family are completed. These ALGORITHM-80 language oriented fro combined design of hardware and programs, multimodule programming language MMP, belonging to the parallel algorithmic level, and arithmetic macroconveyor language AMC, belonging to the problem functional level and oriented to computational mathematics. The latter two languanges are to be used for recursive computer programming [17].Translated from Kibernetika, No. 1, pp. 1–7, January–February, 1981.     

Markovian and analytical models for multiple bus multiprocessor systems with memory blockings

This paper deals with the performance evaluation of asynchronous multiple bus multiprocessor systems where memory modules are temporarily unavailable to processor requests. Such systems cannot be modelled with a product-form queueing network (QN) model because of memory blockings. In this context, we first propose an exact continuous-time Markovian QN model for analyzing small size systems. In order to study medium to large size systems, we also propose several approximate lumped Markovian models and two approximate analytical QN models. The robustness of these approximate models is studied when any memory module gets systematically blocked after each access to this memory module. Results are compared against those obtained either with the exact Markovian QN model or with a stochastic simulation model.     

Comparison of five multiprocessor systems

This paper generalizes the traditional dataflow model of computation and defines the essential problems in multiprocessing: control implementation, program partitioning, scheduling, synchronization, and memory access. The paper assumes that these essential problems are axes of a multiprocessor design space and that the solutions to these problems are values on the axes. Each point in the space represents a multiprocessor including a computational paradigm that a user must follow to achieve high performance and efficiency on the particular machine. Thus, a classification of machines from the user's point of view is introduced naturally. Five well-known multiprocessors are compared using this classification scheme.     

Dynamic partitioning of multiprocessor systems

Partitioning of processors on a multiprocessor system involves logically dividing the system into processor partitions. Programs can be executed in the different partitions in parallel. Optimally setting the partition size can significantly improve the throughput of multiprocessor systems. The speedup characteristics of parallel programs can be defined by execution signatures. The execution signature of a parallel program on a multiprocessor system is the rate at which the program executes in the absence of other programs and depends upon the number of allocated processors, the specific architecture, and the specific program implementation. Based on the execution signatures, this paper analyzes simple Markovian models of dynamic partitioning. From the analysis, when there are at most two multiprocessor partitions, the optimal dynamic partition size can be found which maximizes throughput. Compared against other partitioning schemes, the dynamic partitioning scheme is shown to be the best in terms of throughput when thereconfiguration overhead is low. If the reconfiguration overhead is high, dynamic partitioning is to be avoided. An expression for the reconfiguration overhead threshold is derived. A general iterative partitioning technique is presented. It is shown that the technique gives maximum throughput forn partions.     

Mapping graphs Of parallel programs onto graphs of distributed computer systems by recurrent neural networks

A problem of mapping graphs of parallel programs onto graphs of distributed computer systems by recurrent neural network is formulated. Parameter values providing absence of incorrect solutions are experimentally determined. Because of introduction of penalty coefficient into Lyapunov function for the program graph edges non-coincided with the system graph edges, optimal solutions are found for mapping a “line”-graph onto a two-dimensional torus. For increasing probability of finding optimal mapping, a method for splitting the mapping is proposed. The method essence is a reducing solution matrix to a block-diagonal form. The Wang recurrent neural network is used to exclude incorrect solutions of the problem of mapping the line-graph onto a three-dimensional torus. This network converges quicker than the Hopfield one.     

Using computer controlled physical models to analyze computer integrated manufacturing systems

It is usually difficult to design and install complex computer integrated manufacturing (CIM) systems without a large amount of time spent on debugging. In many cases miniature computer controlled physical models can provide information that reduces the time spent in the design and installation of larger systems. This paper describes how miniature physical models can be used to help industrial engineers design and install CIM systems.