检索结果-内蒙古大学图书馆

10th annual acm-SIAM symposium on Discrete algorithms

作者： Han, YJ Shen, XJ Univ Missouri Sch Interdisciplinary Comp & Engn Kansas City MO 64110 USA

ISBN: (纸本)0898714346

We present a significant improvement for parallel integer sorting. On the EREW (exclusive read exclusive write) PRAM our algorithm sorts n integers in the range {0, 1,..., m 1} in time O(log n) with O(n(q) (log n) over bar /k) operations using word length k log( m + n), where 1 less than or equal to k less than or equal to log n. In this paper we present the following four variants of our algorithm. (1) The first variant sorts integers in {0, 1,..., m - 1} in time O(log n) and in linear space with O(n) operations using word length log m log n. (2) The second variant sorts integers in {0, 1,..., n - 1} in time O ( log n) and in linear space with O(n rootlog n) operations using word length log n. (3) The third variant sorts integers in {0, 1,..., m - 1} in time O(log(3)/(2)n) and in linear space with O(n rootlog n) operations using word length log(m + n). (4) The fourth variant sorts integers in {0, 1,..., m - 1} in time O(log n) and space O(nm(epsilon)) with O(n rootlog n) operations using word length log( m + n). Our algorithms can then be generalized to the situation where the word length is k log( m + n), 1 less than or equal to k less than or equal to log n.

关键词： algorithms analysis of algorithms bucket sorting conservative algorithms design of algorithms integer sorting parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal schedules for cycle-stealing in a network of workstations with a bag-of-tasks workload

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2002年第2期13卷 179-191页

作者： Rosenberg, AL Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

We refine the model underlying our prior work on scheduling bag-of-tasks ("embarrassingly parallel") workloads via cycle-stealing In networks of workstations [5], [17], obtaining a model wherein the scheduling guidelines of [17] produce optimal schedules for every such cycle-stealing opportunity. We thereby render prescriptive the descriptive model of those sources. Although computing optimal schedules usually requires the use of general function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model often suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule-nor even a natural notion of approximately optimal schedule-within the model of [5], [17]. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be "tuned" to accomplish an expected amount of work that is arbitrarily close to optimal.

关键词： cycle-stealing bag-of-tasks workloads heavy-tailed distributions networks of workstations (NOWs) optimal scheduling scheduling parallel computations

来源：评论

学校读者我要写书评

暂无评论

Diffusion schemes for load balancing on heterogeneous networks

Diffusion schemes for load balancing on heterogeneous networ...

引用

12th acm symposium on parallel algorithms and architectures

作者： Elsässer, R Monien, B Preis, R Univ Gesamthsch Paderborn Dept Math & Comp Sci D-33102 Paderborn Germany

Several different diffusion schemes have previously been developed for load balancing on homogeneous processor networks. We generalize existing schemes, in order to deal with heterogeneous networks. Generalized schemes may operate efficiently on networks where each processor can have arbitrary computing power, i.e., the load will be balanced proportionally to these powers. The balancing flow that is calculated by schemes for homogeneous networks is minimal with regard to the l(2)-norm and we prove this to hold true for generalized schemes, too. We demonstrate the usability of generalized schemes by a number of experiments on several heterogeneous networks.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Characterizing and predicting value degree of use 35

Characterizing and predicting value degree of use

引用

35th annual IEEE/acm International symposium on Microarchitecture

作者： Butts, JA Sohi, GS Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

ISBN: (纸本)0769518591

A value's degree of use-the number of dynamic uses of that value-provides the most essential information needed to optimize its communication. We present simulation results demonstrating the properties of degree of use of values, including their predictability: most static instructions generate values with few degrees of use and these exhibit temporal locality. We use these results to guide the design of a degree of use predictor. The development and detailed characterization of this predictor is the focus of this paper. Our predictor leverages future control flow information (e.g., branch predictions) to select among different possible degrees of use. We study the effects of several optimizations and variations in the predictor's algorithms to tune the predictor for maximum performance. The resulting predictor generates correct degree of use predictions for over 92% of all dynamic values and has a misprediction rate below 2.5%. Such a predictor has a wide range of potential applications in optimizing value communication.

关键词： Bandwidth Computational modeling Computer science Delay Design optimization Logic parallel processing Prediction algorithms Predictive models Registers

来源：评论

学校读者我要写书评

暂无评论

A simple and efficient parallel disk mergesort

引用

THEORY OF COMPUTING SYSTEMS 2002年第2期35卷 189-215页

作者： Barve, RD Vitter, JS Winphoria Networks Andheri 400093 Mumbai India Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA

External sorting-the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks-is a fundamental subroutine in database systems [G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K, Section 5.4.9] recently identified SRM (which he calls "randomized striping") as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment [TPI], whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM

关键词：

来源：评论

学校读者我要写书评

暂无评论

A tool based methodology for development of automatically scalable and reusable parallel code 10

A tool based methodology for development of automatically sc...

引用

10th IEEE International symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS 2002)

作者： Murthi, V Levine, D Shirazi, B Marquis, J Univ Texas Dept Comp Sci & Engn Arlington TX 76019 USA

ISBN: (纸本)0769518400

Program performance may be improved by efficiently programming some key sections of the software. In this paper, we present a methodology for converting selected portions of source code into automatically scalable multithreaded routines, without forcing programmers to concentrate on parallel programming issues. These developed routines can be reused across various projects, operating systems and system architectures. To support this methodology two separate but tightly coupled tools have been developed - PARSA(TH) Software Development Environment (SDE) and the ThreadMan(TM) Thread Manager. The SDE addresses programming issues by allowing a graphical object based approach to develop multithreaded routines that abstracts the users from parallel programming. ThreadMan manages the software developed using SDE. ThreadMan is a user-level thread manager that automatically spawns and schedules threads at runtime. Two examples have been developed using this methodology to demonstrate that there is virtually no degradation in performance when compared to sequential code, in a single processor system and scalability is achieved as the number of processors is increased.

关键词： parallel programming

来源：评论

学校读者我要写书评

暂无评论

Coarse-grain pipelining on multiple FPGA architectures 10

Coarse-grain pipelining on multiple FPGA architectures

引用

10th annual IEEE symposium on Field-Programmable Custom Computing Machines

作者： Ziegler, H So, B Hall, M Diniz, PC Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA

ISBN: (纸本)076951801X

Reconfigurable systems, and in particular, FPGA-based custom computing machines, offer a unique opportunity to define application-specific architectures. These architectures offer performance advantages for application domains such as image processing, where the use of customized pipelines exploits the inherent coarse-grain parallelism. In this paper we describe a set of program analyses and an implementation that map a sequential and un-annotated C program into a pipelined implementation running on a set of FPGAs, each with multiple external memories. Based on well-known parallel computing analysis techniques, our algorithms perform unrolling for operator parallelization, reuse and data layout for memory parallelization and precise communication analysis. We extend these techniques for FPGA-based systems to automatically partition the application data and computation into custom pipeline stages, taking into account the available FPGA and interconnect resources. We illustrate the analysis components by way of an example, a machine vision program. We present the algorithm results, derived with minimal manual intervention, which demonstrate the potential of this approach for automatically deriving pipelined designs from high-level sequential specifications.

关键词： coarse-grain pipelining FPGA-based custom computing machines parallelizing compiler analysis techniques

来源：评论

学校读者我要写书评

暂无评论

Online scheduling of parallel programs on heterogeneous systems with applications to Cilk

Online scheduling of parallel programs on heterogeneous syst...

引用

12th acm symposium on parallel algorithms and architectures

作者： Bender, MA Rabin, MO SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate of its own speed, where communication between processors has a cost, and where all scheduling must be online. This problem has been considered previously in the fields of asynchronous parallel computing and scheduling theory. Our model is a bridge between the assumptions in these fields. We provide a new more accurate analysis of an old scheduling algorithm called the maximum utilization scheduler. Based on this analysis, we generalize this scheduling policy and define the high utilization scheduler. We next focus on the Cilk platform and introduce a new algorithm for scheduling Cilk multithreaded parallel programs on heterogeneous processors. This scheduler is inspired by the high utilization scheduler and is modified to fit in a Cilk context. A crucial aspect of our algorithm is that it keeps the original spirit of the Cilk scheduler. In fact, when our new algorithm runs on homogeneous processors, it exactly mimics the dynamics of the original Cilk scheduler.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Online scheduling of parallel programs on heterogeneous systems with applications to Cilk

引用

THEORY OF COMPUTING SYSTEMS 2002年第3期35卷 289-304页

作者： Bender, MA Rabin, MO SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

关键词： COMPUTER systems parallel programming (Computer science)

来源：评论

学校读者我要写书评

暂无评论

A simple and efficient parallel disk mergesort

A simple and efficient parallel disk mergesort

引用

11th annual acm symposium on parallel algorithms and architectures

作者： Barve, RD Vitter, JS Winphoria Networks Andheri 400093 Mumbai India Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：