摘要:

AbstractDynamic load balancing is an important technique when developing applications with unpredictable load distribution on distributed memory multicomputers. A tool,Dynamo, that can be used to utilize dynamic load balancing is presented. This tool separates the application from the load balancer and thus makes it possible to easily exchange the load balancer of a given application and experiment with different load balancing strategies. A prototype of Dynamo has been implemented in the C language on an Intel iPSC/2 Hypercube. Dynamo is demonstrated by two example programs. The first program solves theNqueen problem using a backtracking algorithm and the second solves a 0‐1 knapsack problem using a depth‐first branch and bound algori

ISSN:1040-3108    

DOI:10.1002/cpe.4330060802

出版商:John Wiley&Sons, Ltd    

年代:1994

数据来源: WILEY

摘要:

AbstractThe paper presents the implementation of a new class of massively parallel algorithms for solving certain time‐dependent partial differential equations (PDEs) on massively parallel supercomputers. Such PDEs are usually solved numerically, by discretization in time and space, and by applying a time‐stepping procedure to data and algorithms potentially parallelized in the spatial domain. In a radical departure from such a strictly sequential temporal paradigm, we have developed a concept of time‐parallel algorithms, which allows the marching in time to be fully parallelized. This is achieved by using a set of transformations based on eigenvalue‐eigenvector decomposition of the matrices involved in the discrete formalism. Our time‐parallel algorithms possess a highly decoupled structure, and can therefore be efficiently implemented on emerging, massively parallel, high‐performance supercomputers, with a minimum of communication and synchronization overhead. We have successfully carried out a proof‐of‐concept demonstration of the basic ideas using a two‐dimensional heat equation example implemented on the Intel Touchstone Delta supercomputer. Our results indicate that linear, and even superlinear, speed‐up can be achieved and maintained for a very large number

ISSN:1040-3108    

DOI:10.1002/cpe.4330060803

出版商:John Wiley&Sons, Ltd    

年代:1994

数据来源: WILEY

摘要:

AbstractThe paper deals with the implementation of global time in multicomputer systems. After a formalization of the synchronization problem, techniques to estimate the synchronization delay and to compensate the drift error are proposed. Then SYNC_WAVE, a clock synchronization algorithm where the values of a reference clock are diffused in a wave‐like manner, is described. SYNC_WAVE has no provision for fault‐tolerance and is specially designed to introduce low CPU and communication overhead, in order to support performance analysis applications efficiently. An implementation of the devised algorithm in a transputer‐based system is presented, showing the accuracy results obtained. Finally SYNC_WAVE is compared to other synchronization algorithms and several of its possible applications are sugg

ISSN:1040-3108    

DOI:10.1002/cpe.4330060804

出版商:John Wiley&Sons, Ltd    

年代:1994

数据来源: WILEY

摘要:

AbstractThe paper is concerned with the design and implementation of a parallel dynamic programming algorithm for use in ship voyage management The basic concepts are presented in terms of a simple model for weather routing. Other factors involved in voyage management, and their inclusion in a more comprehensive algorithm, are also discussed. The algorithms have been developed and implemented using a transputer‐baseddistributed‐memoryparallel machine using the high‐level communication harness CS Tools. Trial calculations over grids of up to 282 nodes have been carried out and the results are presented. Good speed‐ups for the calculations have been attained, and the factors affecting the efficiency of the parallel computations are reviewed. These trial calculations indicate that a ship voyage management system based on parallel dynamic programming is likely to be ben

ISSN:1040-3108    

DOI:10.1002/cpe.4330060805

出版商:John Wiley&Sons, Ltd    

年代:1994

数据来源: WILEY

ISSN:1040-3108    

DOI:10.1002/cpe.4330060801

出版商:John Wiley&Sons, Ltd    

年代:1994

数据来源: WILEY