Loop coalescing and scheduling for barrier MIMD architectures

Barrier MIMD's are asynchronous multiple instruction stream, multiple data stream architectures capable of parallel execution of variable execution time instructions and arbitrary control flow (e.g., while loops and calls); however, they differ from conventional MIMD's in that the need for run-time synchronization is significantly reduced. The authors consider the problem of scheduling nested loop structures on a barrier MIMD. The basic approach employs loop coalescing, a technique for transforming a multiply-nested loop into a single loop. Loop coalescing is extended to nested triangular loops, in which inner loop bounds are functions of outer loop indices. In addition, a more efficient scheme to generate the original loop indices from the coalesced index is proposed for the case of constant loop bounds. These results are general, and can be applied to extend previous work using loop coalescing techniques. The authors concentrate on using loop coalescing for scheduling barrier MIMDs, and show how previous work in loop transformations and linear scheduling theory can be applied to this problem     

Pragmatic integrated scheduling for clustered VLIW architectures

Clustered architecture processors are preferred for embedded systems because centralized register file architectures scale poorly in terms of clock rate, chip area, and power consumption. Scheduling for clustered architectures involves spatial concerns (where to schedule) as well as temporal concerns (when to schedule). Various clustered VLIW configurations, connectivity types, and inter‐cluster communication models present different performance trade‐offs to a scheduler. The scheduler is responsible for resolving the conflicting requirements of exploiting the parallelism offered by the hardware and limiting the communication among clusters to achieve better performance. In this paper, we describe our experience with developing a pragmatic scheme and also a generic graph‐matching‐based framework for cluster scheduling based on a generic and realistic clustered machine model. The proposed scheme effectively utilizes the exact knowledge of available communication slots, functional units, and load on different clusters as well as future resource and communication requirements known only at schedule time. The proposed graph‐matching‐based framework for cluster scheduling resolves the phase‐ordering and fixed‐ordering problem associated with earlier schemes for scheduling clustered VLIW architectures. The experimental evaluation in the context of a state‐of‐art commercial clustered architecture (using real‐world benchmark programs) reveals a significant performance improvement over the earlier proposals, which were mostly evaluated using compiled simulation of hypothetical clustered architectures. Our results clearly highlight the importance of considering the peculiarities of commercial clustered architectures and the hard‐nosed performance measurement. Copyright © 2007 John Wiley & Sons, Ltd.     

Static load balancing for a parallel ray tracing on a MIMD hypercube

A parallel ray tracing algorithm is presented. It subdivides the seene into 3D regions, the adjacency of which is modelled by a connectivity graph of regions. Since with each region is associated a ray tracing process, this graph becomes a graph of processes, the edges of which represent the communications between processes. This graph of processes is suitably mapped onto a hypercube topology so as to minimize the communication cost. Static load balancing is performed and solutions are brought to the problems of network congestion and termination.This work has been supported byC ³ and by the CCETT (Centre Commun d'Etudes de Télédiffusion et Télécommunications) under contract 86ME46     

The multiflow trace scheduling compiler

The Multiflow compiler uses the trace scheduling algorithm to find and exploit instruction-level parallelism beyond basic blocks. The compiler generates code for VLIW computers that issue up to 28 operations each cycle and maintain more than 50 operations in flight. At Multiflow the compiler generated code for eight different target machine architectures and compiled over 50 million lines of Fortran and C applications and systems code. The requirement of finding large amounts of parallelism in ordinary programs, the trace scheduling algorithm, and the many unique features of the Multiflow hardware placed novel demands on the compiler. New techniques in instruction scheduling, register allocation, memory-bank management, and intermediate-code optimizations were developed, as were refinements to reduce the overhead of trace scheduling. This article describes the Multiflow compiler and reports on the Multiflow practice and experience with compiling for instruction-level parallelism beyond basic blocks.     

Efficient instruction scheduling using finite state automata

Modern compilers employ sophisticated instruction scheduling techniques to shorten the number of cycles taken to execute the instruction stream. In addition to correctness, the instruction scheduler must also ensure that hardware resources are not oversubscribed in any cycle. For a contemporary processor implementation with multiple pipelines and complex resource usage restrictions, this is not an easy task. The complexity involved in reasoning about such resource hazards is one of the primary factors that constrain the instruction scheduler from performing certain kinds of transformations that can result in improved schedules. We extend a technique for detecting pipeline resource hazards based on finite state automata, to support the efficient implementation of such transformations that are essential for aggressive instruction scheduling beyond basic blocks. Although similar code transformations can be supported by other schemes such as reservation tables, our scheme is superior in terms of space and time. A global instruction scheduler using these techniques was implemented in the KSR compiler. This work was begun while the authors were at Kendall Square Research (KSR).     

Buffering for vector performance on a pipelined MIMD machine

A technique is presented for obtaining vector performance from a pipelined MIMD computer that does not have hardwired vector instructions. The specific computer in mind is the Denelcor HEP, but the technique might influence the use and possibly even the design of future machines with this type of architecture. This preliminary report presents the basic idea and demonstrates that it can be implemented. Buffering blocks of data to registers is used in conjunction with pipelined floating-point operations to achieve vector performance. Empirical evidence is presented to show that up to 5.8 megaflop performance is possible from the Denelcor HEP on very regular tasks such as matrix vector products. While this rate is not in the ‘super-computer’ range, it is certainly respectable given the hardware capabilities of the HEP (this machine is rated at 10 MIPS peak). This performance indicates that an apparently minor refinement to the architectural design could provide very efficient vector operations in addition to the parallelism and low-overhead synchronization already offered by the HEP architecture.     

面向VLIW结构的寄存器压力敏感表调度算法*

为了改善寄存器压力问题,提出一种寄存器压力敏感的指令调度算法。该算法在传统表调度算法的基础上采用关键路径为优先级函数,并考虑在寄存器压力区域内调整非关键节点的调度时机,在应用程序性能不损失的情况下达到了减小寄存器压力的目的。     

A simulator for MIMD performance prediction: application to the S-1 MkIIa multiprocessor

We describe a MIMD multiprocessor simulator and application of that simulator to a multiprocessor of current interest, the S-1 MkIIa. The simulator runs on the CRAY-1 and is designed so that computational physics benchmarks are actually run and produce results. Simulator output from this run is fed into a second level (hardware) simulator which calculates the behavior of the multiprocessor. The simulator can simulate multiprocessors whose basic architecture is that of a few, large processors with or without data caches, sharing global memory through an interconnection switch. The simulator is applied to the investigation of the behavior of four problems on the S-1: The benchmark physics code SIMPLE, a conjugate gradient linear algebra problem, a simple Monte-Carlo problem, and a new method for neutron transport calculations.     

Two algorithms for barrier synchronization

We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of then processes meeting at the barrier must be assigned identifiersi such that 0i<n.     

Task scheduling of parallel programs to optimize communications for cluster of SMPs

This paper discusses the compile time task scheduling of parallel program running on cluster of SMP workstations. Firstly, the problem is stated formally and transformed into a graph parti-tion problem and proved to be NP-Complete. A heuristic algorithm MMP-Solver is then proposed to solve the problem. Experiment result shows that the task scheduling can reduce communication over-head of parallel applications greatly and MMP-Solver outperforms the existing algorithms.     

网络处理器同步问题的编译优化方法

网络处理器具有并行体系结构,而其高级语言往往具有串行语义。对串行程序进行并行化编译要求引入同步,而同步的优劣又影响生成代码的执行效率。针对网络处理器上的程序,提出一个对同步进行优化的程序划分算法以增加程序的并行性。实验数据表明,在一些有代表性的网络应用上,该算法可提高程序的并行性,并提升性能。     

本地多行栅栏覆盖节点活跃调度协议

为了满足沿海泥滩等复杂自然环境中入侵监测系统的需要,改进了栅栏覆盖网络模型,提出了一种本地多行栅栏覆盖调度协议k-MLBCSP,设计了覆盖规划算法与覆盖调整算法。k-MLBCSP协议将网络生命期分为三个阶段,覆盖规划算法保证了初始化阶段网络的合理设置,覆盖调整算法提供了调整阶段sink节点与存活传感器节点进一步协商覆盖规划策略的有效方法。理论分析与仿真结果表明,相比于LBCP、RIS等协议,k-MLBCSP协议提高了网络覆盖率与网络生存期,且节点计算复杂度低,网络负载小。     

Hadoop平台的多队列作业调度优化方法研究

对Hadoop平台的作业调度算法进行了研究, 提出了支持作业类型区分的多队列调度优化算法。优化算法支持根据节点当前的负载情况分配不同类型的作业, 以提高节点的资源利用率; 允许作业队列的资源在闲置时被其他作业队列占用; 在原作业队列需要时可以被即时回收, 即回收过程支持任务抢占; 采用共享队列列表和非共享队列列表的逻辑划分来防止乒乓效应。Hadoop平台的性能测试结果表明, 优化算法相比系统默认算法在作业调度的执行效率、执行平稳性等方面都有了显著的提升。     

WSN中一种流水式栅栏调度算法的研究

无线传感器网络栅栏覆盖为了延长网络的生存时间而需要设计合理的调度算法,通过将传感器网络中的节点进行状态(休眠状态、激活状态等)的切换可达到节省能量的目的。针对入侵者以低速通过栅栏的情况,提出了一种流水式的栅栏调度算法,通过将栅栏均匀分割,将均分后的子栅栏按顺序轮替激活,形成流水式工作状态。入侵者通过监测区域具有较大概率被激活状态的子栅栏监测。分析了基于概率感知模型的栅栏检测率以及栅栏生存时间,最后实验验证了该文算法的准确性和可靠性。     

改进的指令总线功耗优化策略

针对编译器系统设计和编译中的低功耗优化,基于可重定向编译器,实现在编译器后端对VLIW指令总线进行功耗优化的策略.通过对编译生成的二进制目标码进行横向再调度来减少指令总线上的高低电位切换次数,达到降低系统功耗的目的.对编译后端的软件流水和超块调度两种性能优化策略进行对比实验,表明其优化效果在30%以上,并且代码的指令级并行性(Instruction Level Parallelism,ILP)与优化效果存在明显的相关性.最后,通过ILP对该策略提出改进,以指令级并行信息指导功耗优化,在功耗优化效果损失不大的前提下,可节省多达20%的算法开销.     

History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence

In this paper, we extend job scheduling models to include aspects of history-dependent scheduling, where setup times for a job are affected by the aggregate activities of all predecessors of that job. Traditional approaches to machine scheduling typically address objectives and constraints that govern the relative sequence of jobs being executed using available resources. This paper optimises the operations of multiple unrelated resources to address sequential and history-dependent job scheduling constraints along with time window restrictions. We denote this consolidated problem as the general precedence scheduling problem (GPSP). We present several applications of the GPSP and show that many problems in the literature can be represented as special cases of history-dependent scheduling. We design new ways to model this class of problems and then proceed to formulate it as an integer program. We develop specialized algorithms to solve such problems. An extensive computational analysis over a diverse family of problem data instances demonstrates the efficacy of the novel approaches and algorithms introduced in this paper.     

改进细菌觅食算法求解车间作业调度问题*

针对细菌觅食算法（BFOA）求解高维优化问题时容易陷入局部最优和早熟的问题,引入自适应步长及差分进化算子,并将改进算法用于车间作业调度问题（JSP）中。求解时,设计了一种编码转换方案,从而无须修改BFOA运算规则即可实现对JSP的寻优;同时,采用空闲时间片段优化策略降低了调度问题的复杂性。仿真实验表明,该算法能够跳出局部最优,避免了早熟的问题,调度结果优于原始细菌觅食算法和离散粒子群算法。     

Predecessor/successor approach for high-performance run-time wavefront scheduling

Most scientific applications rely on parallel multiprocessor computing to enhance performance. However, the irregular loops within these applications obstruct the parallelism analysis at compile-time. Rauchwerger et al. presented a run-time method to extract the hidden parallelism in a program using dependence chains. The relative overhead degrades this approach’s performance due to the mass storage requirement and huge array reference processing. In this study, a new predecessor/successor approach is developed in which high-level predecessor/successor information is recorded and processed efficiently. A predecessor/successor table is constructed first in the inspector phase so that only the successor iterations in the current wavefront need to be examined, instead of the entire loop iterations during wavefront scheduling. Usually, the performance of dependence chain approach degrades dramatically for a hot-spot access pattern, but our scheme works very efficiently in this case. The experimental results using synthetic code and real programs are presented to prove the superiority of the proposed approach.     

利用Java即时编译器自动外提循环中的同步操作

同步开销是影响并行程序性能的一个重要方面,如果同步操作出现在循环中,将会使这种影响进一步扩大.为了降低循环中同步操作的开销,本文提出一种利用即时编译器外提Java程序中循环内同步操作的优化算法,并在实际的Java虚拟机中实现.该算法在保证程序语义不变的前提下,大量减少运行时实际执行的同步操作数量,降低同步开销,并能保证外提变换后同步代码块不会太大而降低程序的并发度.实验结果表明该算法能提高程序的整体性能,并且不降低程序的可扩放性.