The Cell Broadband Engine: Exploiting Multiple Levels of Parallelism in a Chip Multiprocessor

As CMOS feature sizes continue to shrink and traditional microarchitectural methods for delivering high performance (e.g., deep pipelining) become too expensive and power-hungry, chip multiprocessors (CMPs) become an exciting new direction by which system designers can deliver increased performance. Exploiting parallelism in such designs is the key to high performance, and we find that parallelism must be exploited at multiple levels of the system: the thread-level parallelism that has become popular in many designs fails to exploit all the levels of available parallelism in many workloads for CMP systems. We describe the Cell Broadband Engine and the multiple levels at which its architecture exploits parallelism: data-level, instruction-level, thread-level, memory-level, and compute-transfer parallelism. By taking advantage of opportunities at all levels of the system, this CMP revolutionizes parallel architectures to deliver previously unattained levels of single chip performance. We describe how the heterogeneous cores allow to achieve this performance by parallelizing and offloading computation intensive application code onto the Synergistic Processor Element (SPE) cores using a heterogeneous thread model with SPEs. We also give an example of scheduling code to be memory latency tolerant using software pipelining techniques in the SPE. This paper is based in part on “Chip multiprocessing and the Cell Broadband Engine”, ACM Computing Frontiers 2006.     

GUI录制回放技术在分布并行计算中的研究与应用

GUI录制回放技术在软件测试自动化领域有着广泛的应用,而这里主要讨论了将该技术运用在分布并行计算中.目前,很多软件其自身已经集成了很好的算法,但由于这些软件是非开源的,所以无法直接将这些算法并行化.利用GUI录制回放技术设计并实现了一套工具;使用这套工具并结合特定的分布式计算平台,并行程序开发人员能够方便快速地将这些软件并行化,并将精力放在并行算法的设计上.     

一种非可规约循环的投机并行方法

传统的并行编译器在处理非可规约循环时一般使用结点分割法,但由此带来的代码复制是不可避免的。本文使用投机的方法来挖掘非可规约循环的并行性,该方法在编译时查找程序中的非可规约循环,在运行时使用＂持续引用＂策略预测该循环的入口,进而实现非可规约循环的并行化。     

基于推理多线程技术的一种改进模型

为了解决多线程处理器不同线程之间并行性低、相互之间数据依赖性高的问题，在推理多线程技术基础上提出了一种新的多线程技术模型(分级多线程Hierarchical Multithreading HMT).该模型采用两种等级处理元的方法，低等级使用指令级并行和细粒度线程级并行；高等级更多地使用间隔并行机制.通过详细的模拟研究，证明分级多线程技术通过对线程的不同粒度采用并行机制能够切实可行地提高线程之间的并行性.     

Efficient embedded code generation with multiple load/store instructions

In a recent study, we discovered that many single load/store operations in embedded applications can be parallelized and thus encoded simultaneously in a single‐instruction multiple‐data instruction, called the multiple load/store (MLS) instruction. In this work, we investigate the problem of utilizing MLS instructions to produce optimized machine code, and propose an effective approach to the problem. Specifically, we formalize the MLS problem, that is, the problem of maximizing the use of MLS instructions with an unlimited register file size. Based on this analysis, we show that we can solve the problem efficiently by translating it into a variant of the problem finding a maximum weighted path cover in a dynamic weighted graph. To handle a more realistic case of the finite size of the register file, our solution is then extended to take into account the constraints of register sequencing in MLS instructions and the limited register resource available in the target processor. We demonstrate the effectiveness of our approach experimentally by using a set of benchmark programs. In summary, our approach can reduce the number of loads/stores by 13.3% on average, compared with the code generated from existing compilers. The total code size reduction is 3.6%. This code size reduction comes at almost no cost because the overall increase in compilation time as a result of our technique remains quite minimal. Copyright © 2007 John Wiley & Sons, Ltd.     

异构多核上多级并行模型支持及性能优化

低功耗及廉价性使得异构多核在超级计算机计算资源中占有重要比例.然而,异构多核具有高带宽及松耦合一致性等特点,获得理想的存储及计算性能需要更多地考虑底层硬件细节.实现了一种针对典型的异构多核Cell BE 处理器的多级并行模型CellMLP,通过C 语言扩展编译指导语句,实现了对数据并行、任务并行以及流水并行编程模型的支持,提高了并行程序生产率.运行支持优化方面,数据并行采用SPE 并行数据传输、双缓冲等优化手段来提高数据传输带宽;任务并行使用一种新式混合任务队列以支持异步任务窃取,降低SPE 线程间竞争,提高了任务并行的可扩展性;流水并行首次使用阻塞信号传输机制实现SPE 线程间的低开销同步操作.实验对Stream,NASBenchmark 及BOTS 等应用进行了测试,结果表明,CellMLP 可对多种典型并行应用进行高效支持.与目前同类编程模型SARC 及CellSs 进行性能对比,其结果表明,CellMLP 实际数据传输带宽以及非规则应用的支持方面具有明显优势.     

Construction of optimal algorithms for mass computations in digital filtering problems

Theoretical results are reviewed that are concerned with the construction of speed-optimal parallel-pipeline algorithms for mass calculations in solving filtering problems. The optimality is proved in the corresponding classes of algorithms equivalent in terms of information graphs. The effectiveness of using the developed algorithmic constructions for filtering problems is investigated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 3–14, July–August 2008.     

温度对平晶平面度影响的定性分析及相关问题探讨

在测量平晶工作面的平面度时，温度不仅对平晶平面度的大小有影响，而且直接影响对平晶表面形状（凹凸）的判断。文章给出了温度对平晶平面度影响的实例分析，并提出了两种平晶表面形状判断的辅助方法，且对JJG28—2000《平晶》检定规程中平晶表面形状判断方法进行了必要的补充说明。     

Transforming generate-and-test programs to execute under committed-choice AND-parallelism

This paper concerns the exploitation of user transparent inherent parallelism of pure Prolog programs using program transformation. We describe a novel paradigmenumerate-and-filter for transforming generate-and-test programs for execution under the committed-choice model extended to incorporate multiple solutions based on set enumeration. The paradigm simulates OR-parallelism by stream AND-parallelism integrating OR-parallelism, AND-parallelism, and stream parallelism. Generate-and-test programs are classified into three categories:simple generate-and-test, recursively embedded generate-and-test, and deeply intertwined generate-and-test. The intermediate programs are further transformed to reduce structure copying and metacalls. Algorithms are presented and demonstrated by transforming the representative examples of different classes of generate-and-test programs to Flat Concurrent Prolog equivalents. Statistics show that the techniques are efficient.Funded in part by Cleveland Advanced Manufacturing Program through the State of Ohio as a part of its core research program grant to Center of Automation and Intelligent Systems Research, Case Western Reserve University and NSF equipment grant CDA-8820390 to Kent State University.     

On the promise of general-purpose parallel computing

It has become generally accepted that continued improvements in high-performance scientific computation will be achieved only through the ‘exploitation of parallelism’. Despite the nebulous nature of this expression, enthusiasm for the potential of parallel computing has led to calls for improvements in computational performance of more than a thousand-fold in the next few years, or for what is sometimes referred to as a Teraflop (one trillion floating-point operations per second) Computer. Such a system is envisioned as a general-purpose tool for accelerating progress in such widely varied applications as astronomy, biochemistry, circuit analysis, computational fluid dynamics, global economic modeling, high energy physics, materials science, structural analysis, and weather prediction.

Although parallel architectures appear to offer the greatest promise for significant improvements in overall computational performance, it is not yet clear whether a general-purpose parallel architecture can realize the large increases solicited by the scientific community. This note will take a practical look at the prospect for general-purpose parallel computation and will consider some of the potential limitations by using a simple parametric model of computational performance.