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

On evil twin networks and the value of limited randomized routing

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2000年第9期11卷 910-925页

作者： Alleyne, BD Scherson, ID PMC Sierra Inc San Jose CA 95110 USA Univ Calif Irvine Dept Informat & Comp Sci Irvine CA 92697 USA Univ Calif Irvine Dept Elect & Comp Engn Irvine CA 92697 USA

A dynamic two-stage Delta network (N inputs and outputs) is introduced and analyzed for permutation routing. The notion of evil twins is introduced and a deterministic procedure is given to route any permutation in no more than 2(1)rootN network cycles. Two limited randomized routing schemes are then analyzed. The first called Single Randomization yields on average at most N (!) over bar + 1 + 1/N (N (!) over bar = O(log N/log log N)(1) and is the greatest integer such that (N (!) over bar) less than or equal to N) network cycles and the second called Multiple Randomization yields on average at most right perpendicular log(log N + 1) left perpendicular + 2 +1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the above average bounds is then shown to be at most 1/(c+1)! for Single Randomization and 1/N-2 for Multiple Randomization, respectively. It is then shown how the dynamic two-stage network can be physically realized as a three-stage network. Both the evil twin and Multiple Randomization algorithms have been integrated into an off-the-shelf ASIC from PMC-Sierra, Inc. (PM-73488) which has been designed as a building block for such a three-stage implementation. These routing schemes are also adapted to run on a recirculating network. Recirculation is used to effect a reshuffling of data as in the dynamic network, but with a considerable reduction in network cost.

关键词： multistage interconnection networks (MINs) permutation routing Clos networks Delta networks randomized routing recirculating networks simd computers

来源：评论

学校读者我要写书评

暂无评论

Synthesizing variable instruction issue interpreters for implementing functional parallelism on simd computers

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第4期8卷 412-423页

作者： AbuGhazaleh, NB Wilsey, PA Fan, XZ Hensgen, DA USN POSTGRAD SCHDEPT COMP SCIMONTEREYCA 93943

Functional parallelism can be supported on simd machines by interpretation. Under such a scheme, the programs and data of each task are loaded on the processing elements (PEs) and the Control Unit of the machine executes a central control algorithm that causes the concurrent interpretation of the tasks on the PEs. The central control algorithm is, in many respects, analogous to the control store program on microprogrammed machines. Accordingly, the organization of the control algorithm greatly influences the performance of the synthesized MIMD environment. Most central control algorithms are constructed to interpret the execution phase of all instructions during every cycle (iteration). However, it is possible to delay the interpretation of infrequent and costly instructions to improve the overall performance. Interpreters that attempt improved performance by delaying the issue of infrequent instructions are referred to as variable issue control algorithms. This paper examines the construction of optimized variable issue control algorithms. In particular, a mathematical model for the interpretation process is built and two objective functions (instruction throughput and PE utilization) are defined. The problem of deriving variable issue control algorithms for these objective functions has been shown elsewhere to be NP-complete. Therefore, this paper investigates three heuristic algorithms for constructing near optimal variable issue control algorithms. The performance of the algorithms is studied on four different instruction sets and the trends of the schedulers with respect to the instruction sets and the objective functions are analyzed.

关键词： MIMD on simd interpretation variable instruction issue scheduling instruction execution simd computers

来源：评论

学校读者我要写书评

暂无评论

A system for evaluating performance and cost of simd array designs 7

A system for evaluating performance and cost of SIMD array d...

引用

7th Symposium on the Frontiers of Massively Parallel Computation (Frontiers 99)

作者： Herbordt, MC Cravy, J Sam, R Kidwai, O Lin, C Univ Houston Dept Elect & Comp Engn Houston TX 77204 USA

ISBN: (纸本)0769500870

simd arrays are likely to become increasingly important as coprocessors in domain specific systems as architects continue to leverage RAM technology in their design. The problem this work addresses is the evaluation of simd arrays with respect to complex applications while accounting for operating frequency and chip area. The method we use is to bridge the gap between architecture-level and EDA-level modeling by using an EDA-based tool to calibrate architectural simulations. The resulting system retains much of the high throughput of the architecture-level simulator but also has accuracy similar to that of an early pass EDA synthesis and circuit simulation. We have used our system to evaluate hundreds of potential simd array designs with respect to real applications. Some of the results were surprising: the slowdown caused by underutilized resources was significantly more than we had anticipated.

关键词： simd computers parallel computer architecture computer design evaluation computer simulation domain specific systems

来源：评论

学校读者我要写书评

暂无评论

MAPPING QR DECOMPOSITION ON PARALLEL computers - A STUDY CASE FOR RADAR APPLICATIONS

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 1994年第10期E77B卷 1264-1271页

作者： DACIERNO, A CECCARELLI, M FARINA, A PETROSINO, A TIMMONERI, L ALENIA AERITALIA & SELENIA DEPT RADAR ENGN RADAR SYST ANAL GRP I-00131 ROME ITALY

The sidelobe canceler in radar systems is a highly computational demanding problem. It can be efficiently tackled by resorting to the QR decomposition mapped onto a systolic array processor. The paper reports several mapping strategies by using massive parallel computers available on the market. MIMD as well as simd machines have been used, specifically MEIKO Computing Surface, nCUBE2, Connection Machine CM-200, and MasPar MP-1. The achieved data throughput values have been measured for a number of operational situations of practical interest.

关键词： RADAR SIDELOBE CANCELER QR DECOMPOSITION PARALLEL PROCESSING SYSTOLIC ARRAY MIMD computers simd computers

来源：评论

学校读者我要写书评

暂无评论

ORDER-STATISTICS ON OPTICALLY INTERCONNECTED MULTIPROCESSOR SYSTEMS

引用

OPTICS AND LASER TECHNOLOGY 1994年第4期26卷 281-287页

作者： PAN, Y The author is in the Department of Computer Science University of Dayton Dayton OH 45469-2160 USA

Processor arrays with an optical bus are introduced for parallel computation in this paper. We use the order statistics problem as an example to demonstrate how to design efficient parallel algorithms on such systems. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Time analysis indicates that order statistics can be done more efficiently on a linear array with a pipelined optical bus than with an electronic bus. The initial results are promising, and the author believes that optical buses may emerge as a powerful communication mechanism for connecting large parallel computer systems in the near future.

关键词： PIPELINED OPTICAL BUSES PARALLEL ALGORITHMS simd computers

来源：评论

学校读者我要写书评

暂无评论

TOWARDS FIRST-PRINCIPLES THEORIES OF MATERIALS AND BIOLOGICAL-SYSTEMS - THE NEED FOR MASSIVE PARALLELISM

引用

FUTURE GENERATION COMPUTER SYSTEMS 1994年第2-3期10卷 331-338页

作者： WILLE, LT ROGERS, JL BURMESTER, CP GRONSKY, R UNIV CALIF BERKELEY DEPT MAT SCI & MINERAL ENGNBERKELEYCA 94720 UNIV CALIF BERKELEY LAWRENCE BERKELEY LABDIV MAT SCIBERKELEYCA 94720

The first-principles paradigm, i.e. the calculation of a physical, chemical, or biological system's properties without including any fitted or adjustable parameters, is one of the most powerful in the scientist's quest to understand nature. Unfortunately most first-principles computations involve quite complicated governing equations and large system sizes, both of which have a detrimental effect on memory size and computer time requirements. Using two relatively simple yet realistic models, one in materials science and one in biophysics, it is discussed here how massive parallelism can make such studies feasible.

关键词： MASSIVELY PARALLEL COMPUTING simd computers MATERIALS SCIENCE BIOPHYSICS PARALLEL MONTE CARLO SIMULATION CHAOS

来源：评论

学校读者我要写书评

暂无评论

PARALLEL CONTEXT-SENSITIVE COMPILATION

引用

SOFTWARE-PRACTICE & EXPERIENCE 1994年第9期24卷 801-822页

作者： ASTHAGIRI, CR POTTER, JL KENT STATE UNIV DEPT MATH & COMP SCIKENTOH 44242

The searching power of massively parallel associative computers is an under used and under investigated capability that can be used to facilitate software development. This paper describes the development of a context sensitive compiler for pattern-matching languages using that searching power. The described compiler was implemented on the STARAN parallel computer and the compiled OPS5 programs were also executed on the STARAN obtaining an estimated throughput of 6000 rules per second. The described compilation of production rules into equivalent procedural rules is completely data parallel, with the degree of parallelism depending on the number of tokens in the program being compiled. During any one step of the context-sensitive analysis, the entire program is processed in constant time.

关键词： CONTEXT-SENSITIVE COMPILATION MASSIVE PARALLELISM ASSOCIATIVE PROCESSING simd computers PATTERN MATCHING

来源：评论

学校读者我要写书评

暂无评论

simd MATRIX-METHODS FOR DETECTING HAZARDS IN LOGIC-CIRCUITS

引用

IEE PROCEEDINGS-E computers AND DIGITAL TECHNIQUES 1993年第4期140卷 201-204页

作者： HEAL, BW PAGE, RMR Department of Information Science University of Portsmouth Portsmouth UK

The paper describes the underlying theory and an outline for an algorithm which is designed to utilise the power of simd computers to detect and locate the presence of logic hazards in combinational logic circuits.

关键词： COMBINATORIAL LOGIC CIRCUITS ALGORITHMS simd computers MATRIX ALGEBRA HAZARDS

来源：评论

学校读者我要写书评

暂无评论

SUPERPARALLEL-FFTS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1993年第2期14卷 349-367页

作者： MUNTHEKAAS, H CTR EUROPEEN RECH & FORMAT AVANCEE CALCUL SCI TOULOUSEFRANCE

Fast Fourier transform (FFT) algorithms for single instruction multiple data (simd) machines are developed which simultaneously solve any combination of FFTs of different sizes and even different spatial dimensionalities. The only restrictions are that all the periods must be powers of two and that the initial data must satisfy some alignment requirements with the address space in the computer. The degree of parallelism is equal to the sum of the sizes of all the subproblems and the (parallel) solution time is proportional to log2(m), where m is the number of points in the largest subsystem. It is shown that the task of unscrambling the data can be both executed and scheduled efficiently in parallel. Finally, implementations on the MasPar computer are described. The codes can be quickly and easily employed in solving complicated problems, and the interface for the routines may therefore be interesting for sequential FFT codes as well.

关键词： FFT PARALLEL COMPUTING simd computers SUPERPARALLEL ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

ODD MEMORY-SYSTEMS MAY BE QUITE INTERESTING

ODD MEMORY-SYSTEMS MAY BE QUITE INTERESTING

引用

20TH ANNUAL INTERNATIONAL SYMP ON COMPUTER ARCHITECTURE ( ISCA 93 )

作者： SEZNEC, A LENFANT, J IRISA Rennes France

ISBN: (纸本)0818638109

Using a prime number N of memory banks on a vector processor allows a conflict-free access for any slice of N consecutive elements of a vector stored with a stride not multiple of N. To reject the use of a prime (or odd) number N of memory banks, it is generally advanced that address computation for such a memory system would require systematic Euclidean Division by the number N. We first show that the well known Chinese Remainder Theorem allows to define a very simple mapping of data onto the memory banks for which address computation does not require any Euclidean Division. Massively parallel simd computers may have several thousands of processors. When the memory on such a machine is globally shared, routing vectors from memory to the processors is a major difficulty;the control for the interconnection network cannot be generally computed at execution time. When the number of memory banks and processors is a product of prime numbers, the family of permutations needed for routing vectors from memory to the processors through the interconnection network have very specific properties. The Chinese Remainder Network presented in the paper is able to execute all these permutations in a single path and may be self-routed.

关键词： PRIME MEMORY SYSTEMS VECTOR simd computers CHINESE REMAINDER NETWORK

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：