Towards a single model of efficient computation in real parallel machines

We propose a model of parallel computation, the YPRAM, that allows general parallel algorithms to be designed for a wide class of parallel models. The basic model captures locality among processors, which is measured as a function of two parameters; latency and bandwidth.

We design YPRAM algorithms for solving several fundamental problems: parallel prefix, sorting, sorting numbers from a bounded range, and list ranking. We show that our model predicts, reasonably accurately, the actual known performances of several basic parallel models — PRAM, hypercube, mesh and tree — when solving these problems.     

Performance measurement,visualization and modeling of parallel and distributed programs using the AIMS toolkit

Writing large-scale parallel and distributed scientific applications that make optimum use of the multiprocessor is a challenging problem. Typically, computational resources are underused due to performance failures in the application being executed. Performance-tuning tools are essential for exposing these performance failures and for suggesting ways to improve program performance. In this paper, we first address fundamental issues in building useful performance-tuning tools and then describe our experience with the AIMS toolkit for tuning parallel and distributed programs on a variety of platforms. AIMS supports source-code instrumentation, run-time monitoring, graphical execution profiles, performance indices and automated modeling techniques as ways to expose performance problems of programs. Using several examples representing a broad range of scientific applications, we illustrate AIMS' effectiveness in exposing performance problems in parallel and distributed programs.     

Models for practical parallel computation

A major reason for the lack of practical use of parallel computers has been the absence of a suitable model of parallel computation. Many existing models are either theoretical or are tied to a particular architecture. A more general model must be architecture independent, must realistically reflect execution costs, and must reduce the cognitive overhead of managing massive parallelism. A growing number of models meeting some of these goals have been suggested. We discuss their properties and relative strengths and weaknesses. We conclude that data parallelism is a style with much to commend it, and discuss the Bird-Meertens formalism as a coherent approach to data parallel programming.This work was supported by the Natural Sciences and Engineering Research Council of Canada.     

粒子模拟中一种非结构化通用并行通信模式的研究和范型实现

中国科学院过程工程研究所多相反应实验室,建立了一个通用粒子模拟平台并已开始应用。目前类似的并行模拟系统采用的Shift并行通信模式往往有一些问题,需要一种新的通信模式来弥补它的不足。本文设计具有良好通用性的非结构化通信模式All2All,用来完成通用粒子方法模拟平台中计算节点问的通信。本文的算例证明这种通信模式可解决在粒子并行模拟Shift通信模式所不能处理的,具有复杂拓扑关系的相邻节点间的数据通信问题。本文设计的All2All通信模式方法只需稍加修改,就可以方便地应用于其它领域的并行计算系统。     

Breaking the data encryption standard using networks of evolutionary processors with parallel string rewriting rules

In this paper we introduce a biologically inspired distributed computing model called networks of evolutionary processors with parallel string rewriting rules (NEPPS), which is a variation of the hybrid networks of evolutionary processors introduced by Martin-Vide et al. Such a network contains simple processors that are located in the nodes of a virtual graph. Each processor has strings (each string having multiple copies) and string rewriting rules. The rules are applied parallely on the strings. After the strings have been rewritten, they are communicated among the processors through filters. We show that we can theoretically break the DES (data encryption standard), which is the most widely used cryptosystem, using NEPPS. We prove that, given an arbitrary <plain-text, cipher-text> pair, one can recover the DES key in a constant number of steps.     

Reducing the cost of IT ownership using feedback from the IT helpdesk

The paper provides a discourse on the use that can be made of data derived from corporate data systems in reducing the cost of ownership of IT. The paper is based on a series of case studies carried out on systems in use at Rolls-Royce and Associates Limited. The case studies draw on data contained in the corporate IT help desk system, and system monitors. It describes the methodology used to draw together metrics for failure and use in determining the whole life cost of IT systems. This is demonstrated through examples of cost improvement initiatives applied to personal computers. The paper concludes with a summary of simple system attributes that can both improve our understanding of the more cost significant system elements, and which can then be used to carry through a TQM cost reduction initiative.