Programmer's Manual for XMTC Language, XMTC Compiler and XMT Simulator (2006)
Balkan, Aydin O., Vishkin, Uzi
Explicit Multi-Threading (XMT) is a computing framework developed at the University of Maryland as part of a PRAM-on-chip vision (http://www.umiacs.umd.edu/users/vishkin/XMT). Much in the same way...
Balkan, Aydin O., Qu, Gang, Vishkin, Uzi
Many applications have stimulated the recent surge of interest single-chip parallel processing. In such machines, it is crucial to implement a high-throughput low-latency interconnection network to...
Programmer's Manual for XMTC Language, XMTC Compiler and XMT Simulator (2006)
Balkan, Aydin O., Vishkin, Uzi
Explicit Multi-Threading (XMT) is a computing framework developed at the University of Maryland as part of a PRAM-on-chip vision (http://www.umiacs.umd.edu/users/vishkin/XMT). Much in the same way...
Balkan, Aydin O., Qu, Gang, Vishkin, Uzi
Many applications have stimulated the recent surge of interest single-chip parallel processing. In such machines, it is crucial to implement a high-throughput low-latency interconnection network to...
Vishkin, Uzi, Caragea, George C., Lee, Bryant
A bold vision that guided this work is as follows: (i) a parallel algorithms and programming course could become a standard course in every undergraduate computer science program, and (ii) this...
Vishkin, Uzi, Caragea, George C., Lee, Bryant
A bold vision that guided this work is as follows: (i) a parallel algorithms and programming course could become a standard course in every undergraduate computer science program, and (ii) this...
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover (2002)
Khuller, Samir, Vishkin, Uzi, Young, Neal
The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).
Contents 1 Preface - A Case for Studying Parallel Algorithms 4 1.1 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 More background and detail : : : : : : : : : : :...
Evaluating the XMT Parallel Programming Model (2001)
Dorit Naishlos, Joseph Nuzman, Chau-wen Tseng, Uzi Vishkin
Explicit-multithreading (XMT) is a parallel programming model designed for exploiting on-chip parallelism. Its features include a simple thread execution model and an efficient prefix-sum instruction...
XMT-M: A Scalable Decentralized Processor (1999)
Efraim Berkovich, Joseph Nuzman, Manoj Franklin, Bruce Jacob, Uzi Vishkin
A defining challenge for research in computer science and engineering has been the ongoing quest for reducing the completion time of a single computation task. Even outside the parallel processing...
XMT-M: A Scalable Decentralized Processor (1999)
Efraim Berkovich, Joseph Nuzman, Manoj Franklin, Bruce Jacob, Uzi Vishkin
A defining challenge for research in computer science and engineering has been the ongoing quest for reducing the completion time of a single computation task. Even outside the parallel processing...
XMT-M: A Scalable Decentralized Processor (1999)
Berkovich, Efraim, Nuzman, Joseph, Franklin, Manoj, Jacob, Bruce, Vishkin, Uzi
A defining challenge for research in computer science and engineering has been the ongoing quest for reducing the completion time of a single computation task. Even outside the parallel processing...
XMT-M: A Scalable Decentralized Processor (1999)
Berkovich, Efraim, Nuzman, Joseph, Franklin, Manoj, Jacob, Bruce, Vishkin, Uzi
A defining challenge for research in computer science and engineering has been the ongoing quest for reducing the completion time of a single computation task. Even outside the parallel processing...
Experiments With List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism (1999)
Algorithms for the problem of list ranking are empirically studied for the Explicit Multi-Threaded (XMT) platform for instruction parallelism. The main goal of this study is to understand the the...
. Algorithms for the problem of list ranking are empirically studied with respect to the Explicit Multi-Threaded (XMT) platform for instruction-level parallelism (ILP). The main goal of this study is...
Trade-offs Between Communication Throughput and Parallel Time (1998)
Yishay Mansour, Noam Nisan, Uzi Vishkin
We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model has p processors...
On Parallel Hashing and Integer Sorting. (1998)
The problem of sorting n integers from a restricted range (1..m), where m is superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m)...
Recursive Star-Tree Parallel Data-Structure. (1998)
The model of parallel computation that is used in this paper is the concurrent-read concurrent-write (CRCW) parallel random access machine (PRAM). We assume that several processors may attempt to...
Uzi Vishkin, Shlomit Dascal, Efraim Berkovich, Joseph Nuzman
This paper envisions an extension to a standard instruction set which efficiently implements PRAM-style algorithms using explicit multi-threaded instruction-level parallelism (ILP); that is, Explicit...
Looking to Parallel Algorithms for ILP and Decentralization (1998)
Berkovich, Efraim, Jacob, Bruce, Nuzman, Joseph, Vishkin, Uzi
We introduce explicit multi-threading (XMT), a decentralized architecture that exploits fine-grained SPMD-style programming; a SPMD program can translate directly to MIPS assembly language using...
Looking to Parallel Algorithms for ILP and Decentralization (1998)
Berkovich, Efraim, Jacob, Bruce, Nuzman, Joseph, Vishkin, Uzi
We introduce explicit multi-threading (XMT), a decentralized architecture that exploits fine-grained SPMD-style programming; a SPMD program can translate directly to MIPS assembly language using...
Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism (1998)
Uzi Vishkin, Shlomit Dascal, Efraim Berkovich, Joseph Nuzman
The paper envisions an extension to a standard instruction set which efficiently implements PRAM algorithms using explicit multi-threaded instruction-level parallelism (ILP); that is, Explicit...
On Parallel Hashing and Integer Sorting (1997)
The problem of sorting n integers from a restricted range [1::m], where m is superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m)...
Randomized Range-Maxima In Nearly-Constant Parallel Time (1997)
Omer Berkman, Yossi Matias, Uzi Vishkin
. Given an array of n input numbers, the range-maxima problem is that of preprocessing the data so that queries of the type "what is the maximum value in subarray [i::j]" can be answered quickly...
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover (1997)
Samir Khuller, Uzi Vishkin, Neal Young
We give an efficient deterministic parallel approximation algorithm for the minimumweight vertex- and set-cover problems and their duals (edge/element packing). The algorithm is simple and suitable...
Parallel Algorithms for Database Operations and a Database Operation for Parallel Algorithms (1997)
This paper establishes some significant links between two areas: (i) relational parallel database systems; and (ii) the design and analysis of parallel algorithms. The paper begins with a fundamental...
A Case for the PRAM As a Standard Programmer's Model (1997)
This position paper advocates that the PRAM model of parallel computation will be a standard (but not exclusive) programmer's model for computers whose hardware features various kinds of parallelism.
Conflict-Free Access to Multiple Single-Ported Register Files (1997)
Silvia M. Mueller, Uzi Vishkin
The paper presents a novel static algorithm for mapping values to multiple register files. The algorithm is based on the edge-coloring of a bipartite graph. It allows the migration of values among...
A novel comprehensive and coherent approach for the purpose of increasing instruction-level parallelism (ILP) is devised. The key new tool in our envisioned system update is the addition of a...
Pattern Matching in a Digitized Image (1997)
For motivation purpose, imagine the following continuous pattern matching problem. Given are two continuous pictures, each consisting of unicolor regions; one picture is called the scene and the...
A novel comprehensive and coherent approach for the purpose of increasing instruction-level parallelism (ILP) is devised. The key new tool in our envisioned system update is the addition of a...
Structural Parallel Algorithmics (1997)
The first half of the paper is a general introduction which emphasizes the central role that the PRAM model of parallel computation plays in algorithmic studies for parallel computers. Some of the...
Silvia M. Mueller, Uzi Vishkin
The paper presents a novel static algorithm for mapping values to multiple register files. The algorithm is based on the edge-coloring of a bipartite graph. It allows the migration of values among...
Tight Comparison Bounds On The Complexity Of Parallel Sorting (1995)
The problem of sorting n elements using p processors in a parallel comparison model is considered. Lower and upper bounds which imply that for p ³ n, the time complexity of this problem is Q( log(1...
Designing a coherent agenda for the implementation of the High Performance Computing (HPC) program is a nontrivial technical challenge. Many computer science and engineering researchers in the area...
Designing a coherent agenda for the implementation of the High Performance Computing (HPC) program is a nontrivial technical challenge. Many computer science and engineering researchers in the area...
Can Parallel Algorithms Enhance Serial Implementation? (1993)
Consider the serial emulation of a parallel algorithm. The thesis presented in this paper is rather broad. It suggests that such a serial emulation has the potential advantage of running on a serial...
Can Parallel Algorithms Enhance Serial Implementation? (1993)
Consider the serial emulation of a parallel algorithm. The thesis presented in this paper is rather broad. It suggests that such a serial emulation has the potential advantage of running on a serial...
A new general parallel algorithmic technique for computations on trees is presented. The new technique performs a reduction of the tree expression evaluation problem to list ranking; then, the list...
Tight Comparison Bounds On The Complexity Of Parallel Sorting (1970)
The problem of sorting n elements using p processors in a parallel comparison model is considered. Lower and upper bounds which imply that for p n, the time complexity of this problem is Q( log(1 + p...