On solving systems of ordinary differential equations on MIMD-computers

The error of solution of Cauchy problems for systems of ordinary differential equations is estimated in the case where the input data are approximate. It is shown how to prepare a program for computing the right-hand sides of the system automatically and simultaneously. Diagrams are presented to illustrate the efficiency of parallelization. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 175–182, March–April 2007.     

Internet拥塞控制系统在不同源控制算法作用下的资源竞争分析

在未来的Internet拥塞控制协议中,不同的用户群根据不同的QoS需求,可以实现不同的控制算法.系统地研究了拥塞控制系统在AIMD和MIMD两类源算法共同作用下的稳态和动态特性,这些特性揭示了配置不同源控制算法的用户群对网络资源的竞争.内容包括AIMD,MIMD算法共同作用下的系统模型、系统稳态分析、系统稳定性分析等.基于NS2系统的仿真结果,证实了给出的分析方法的有效性,并揭示了不同源算法对网络资源的竞争情况.     

基于FPGA的多节点1553B总线协议处理器的实现

研究设计了一种多节点的1553B总线协议处理器,可以模拟整套1553B总线系统,既可以作为测试设备,也可作为总线上的多个节点在实际应用中使用。针对总线协议处理器逻辑与存储资源占用高、难以单片实现的问题,提出了多核MIMD架构的实现思路,有效地降低了逻辑资源的使用量,使其可以在单片FPGA上实现。基于软硬件融合的理念,通过自定义专用指令集增加指令并行度来提高指令执行的效率,增强了系统的实时性,使其可以在低频时钟下运行,从而降低了系统的功耗。     

Mapping Conjugate Gradient Algorithms for Neutron Diffusion Applications onto SIMD, MIMD, and Mixed-Mode Machines

The performance of conjugate gradient (CG) algorithms for the solution of the system of linear equations that results from the finite-differencing of the neutron diffusion equation was analyzed on SIMD, MIMD, and mixed-mode parallel machines. A block preconditioner based on the incomplete Cholesky factorization was used to accelerate the conjugate gradient search. The issues involved in mapping both the unpreconditioned and preconditioned conjugate gradient algorithms onto the mixed-mode PASM prototype, the SIMD MasPar MP-1, and the MIMD Intel Paragon XP/S are discussed. On PASM , the mixed-mode implementation outperformed either SIMD or MIMD alone. Theoretical performance predictions were analyzed and compared with the experimental results on the MasPar MP-1 and the Paragon XP/S. Other issues addressed include the impact on execution time of the number of processors used, the effect of the interprocessor communication network on performance, and the relationship of the number of processors to the quality of the preconditioning. Applications studies such as this are necessary in the development of software tools for mapping algorithms onto either a single parallel machine or a heterogeneous suite of parallel machines.     

The parallel quicksort algorithm part 2—simulation

This paper is the second of a two part series in which a general purpose sorting algorithm i.e. Quicksort is adapated for execution on an M.I.M.D. computer system. In this part, the parallel algorithm derived in Part 1 is simulated and qualitative agreement with the results from the run-time analysis was obtained.     

Static scheduling for barrier MIMD architectures

In a SIMD or VLIW machine, conceptual synchronizations are accomplished by using a static code schedule that does not require run-time synchronization. The lack of run-time synchronization overhead makes these machines very effective for fine-grain parallelism, but they cannot execute parallel code structures as general as those executed by MIMD architectures, and this limits their utility.In this paper we present a timing analysis that allows a compiler for a MIMD machine to eliminate a large fraction of the run-time synchronization by making efficient use of static code scheduling. Although these techniques can be adapted to be applied to most MIMD machines, this paper centers on the analysis and scheduling for barrier MIMD machines. Barrier MIMDs are asynchronous multiple instruction stream/multiple data stream architectures capable of parallel execution of variable execution-time instructions and arbitrary control flow (e.g., while loops and calls). However, they also incorporate a special hardware barrier synchronization mechanism that facilitates static scheduling by providing a mechanism which the compiler can use to enforce precise timing constraints. In other words, the compiler tracks relative timing between processors and uses static code scheduling until the timing imprecision becomes too large, at which point the compiler simply inserts a barrier to reduce that timing imprecision to zero (or a small constant).This paper describes new scheduling and barrier placement algorithms for barrier MIMDs that are based loosely on the list scheduling approach employed for VLIWs [Ellis 1985]. In addition, the experimental results from scheduling thousands of synthetic benchmark programs for a parameterized barrier MIMD machine are presented.     

Mesh-connected parallel computer PAX for scientific applications

Nearest-neighbor-mesh connection plus global broadcasting/control bus characterizes the architecture of the processor array PAX, that was constructed for and is now operating in many typical scientific applications. Not only these inter-processor connections, but also an MIMD structure of the machine were found effective in the particle transport problems, that require asynchronous operation.

The paper describes the bases of architecture of two recent versions of the PAX computer, their hardware and software systems, and, based on the implementation of scientific applications, the effectiveness of the PAX type architecture is presented.     

Hypercube computing: Connected components

Several approaches to finding the connected components of a graph on a hypercube multicomputer are proposed and analyzed. The results of experiments conducted on an NCUBE hypercube are also presented. The experimental results support the analysis.This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.     

A MIMD implementation of a parallel Euler solver for unstructured grids

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a MIMD (multiple instruction/multiple data stream) parallel computer. Three partitioning strategies for distributing the work load onto the processors are discussed. Issues pertaining to the communication costs are also addressed. We find that the spectral bisection strategy yields the best performance. The performance of this unstructured computation on the Intel iPSC/860 compares very favorably with that on a one-processor CRAY Y-MP/1 and an earlier implementation on the Connection Machine.The authors are employees of Computer Sciences Corporation. This work was funded under contract NAS 2-12961     

Comparing shared and distributed memory computers

There are two distinct types of MIMD (Multiple Instruction, Multiple Data) computers: the shared memory machine, e.g. Butterfly, and the distributed memory machine, e.g. Hypercubes, Transputer arrays. Typically these utilize different programming models: the shared memory machine has monitors, semaphores and fetch-and-add; whereas the distributed memory machine uses message passing. Moreover there are two popular types of operating systems: a multi-tasking, asynchronous operating system and a crystalline, loosely synchronous operating system.

In this paper I firstly describe the Butterfly, Hypercube and Transputer array MIMD computers, and review monitors, semaphores, fetch-and-add and message passing; then I explain the two types of operating systems and give examples of how they are implemented on these MIMD computers. Next I discuss the advantages and disadvantages of shared memory machines with monitors, semaphores and fetch-and-add, compared to distributed memory machines using message passing, answering questions such as “is one model ‘easier’ to program than the other?” and “which is ‘more efficient‘?”. One may think that a shared memory machine with monitors, semaphores and fetch-and-add is simpler to program and runs faster than a distributed memory machine using message passing but we shall see that this is not necessarily the case. Finally I briefly discuss which type of operating system to use and on which type of computer. This of course depends on the algorithm one wishes to compute.