可重构多核片上系统体系结构综述

可重构片上多核系统利用不同粒度、不同耦合度的可重构资源,充分开发资源的并行性,兼顾硬件计算的高性能及软件实现的灵活性,且复用特性使其具备开发设计成本降低、产品面市时间缩短的优势。介绍可重构计算系统概念及其分类,从系统级层面回顾可重构多核片上系统体系结构的研究进展,讨论未来的研究趋势及需要关注的关键问题。     

网络处理器体系结构分析

随着网络的发展,网络处理器在构建未来网络系统中发挥着越来越重要的作用。在网络处理器产生的历史背景的基础上,分析了评价其硬件体系结构的主要方面,研究了几种典型的网络处理器的体系结构,总结了网络处理器的总体体系结构特点,阐述了其现有体系结构的发展及下一步的工作。     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

Data token heuristic scheduling of the Kalman algorithm onto a message-passing multiprocessor system

Scheduling the tasks of a parallel algorithm onto a network of processors to minimize the completion time of the task graph is an NP-hard problem, and heuristic methods are commonly used to solve this problem. Published works in this area, however, do not take advantage of the following aspects of the problem: (i) the availability of the full knowledge of the data that is being transferred during inter-task communication, and (ii) the availability of full duplex high-speed communication links in many multiprocessors (such as transputers). The scheduling approach presented in this paper, the data token heuristic (DTH) approach, exploits the above features, leading to a reduced schedule length. This is achieved by checking the pool of data tokens in the processors, and routing the required data token to the processor through the dynamic shortest path. The DTH approach is then used to find the best transputer network topology that gives the minimum schedule length for the parallel implementation of the Kalman algorithm. Quantitative results of scheduling the Kalman algorithm on a 4-transputer network with T-805 transputers are presented.     

多处理器全局单调比率的可调度性分析

针对全局单调比率(RM)调度的多处理器系统中最高优先级任务数量少于处理器数量时,Bertogna等给出的最坏情况计算任务受到的干涉过于悲观,证明了任务受到最高优先级任务的干涉不会出现最坏情况,它受到非最高优先级任务干涉仍可能出现最坏情况。分析得出了任务受到最高优先级任务干涉的最大可能值,由此得到了一个更紧的可调度性判断条件。实验结果表明,提出的方法提高了判为可调度的任务集数量。     

Heuristic fault-tolerant routing strategies for a multiprocessor network

We examine the suitability of three heuristic search algorithms (Greedy Constructive Scheme, Best First Search and A^*) for use as routing strategies on a faulty multiprocessor network. Our search space is a simulated 5 × 5 × 5 (125-node) multiprocessor mesh network. Each virtual node comprises a processor and a communications switch supporting explicit message backtracking. Their performances are compared for up to 20% of randomly generated faulty links. The results show that heuristic search algorithms can be implemented as fault-tolerant routing strategies and that the modified Best First Search routing strategy performed consistently better with significantly less degradation than the Greedy Constructive Scheme and the A^* strategies.     

多处理器调度算法实现及其Petri网建模与仿真

多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

Lower bound algorithms for multiprocessor task scheduling with ready times

In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on‐line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so‐called one‐to‐many transmission. We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios.     

Parallel stereocorrelation on a reconfigurable multi-ring network

A reconfigurable network termed as the reconfigurable multi-ring network (RMRN) is described. The RMRN is shown to be a truly scalable network in that each node in the network has a fixed degree of connectivity and the reconfiguration mechanism ensures a network diameter of O(log₂ N) for anN-processor network. Algorithms for the two-dimensional mesh and the SIMD or SPMD n-cube are shown to map very elegantly onto the RMRN. Basic message passing and reconfiguration primitives for the SIMD/SPMD RMRN are designed for use as building blocks for more complex parallel algorithms. The RMRN is shown to be a viable architecture for image processing and computer vision problems using the parallel computation of the stereocorrelation imaging operation as an example. Stereocorrelation is one of the most computationally intensive imaging tasks. It is used as a visualization tool in many applications, including remote sensing, geographic information systems and robot vision.An earlier version of this paper was presented at the 1995 International Conference on Parallel and Distributed Processing Techniques and Applications.     

基于排队网络的网络服务器性能分析与优化

针对网络服务器在用户数量和状态相对复杂情况下无法对服务器性能进行有效分析的问题,提出了一种基于排队网络的服务器性能分析方法。该方法可以有效降低时间复杂度和空间复杂度,使服务器性能分析更加精确,效率更高。实验结果表明,利用该方法对服务器性能进行建模和分析,并根据分析结果对服务器程序进行优化,可以达到合理利用系统资源、提高服务器性能的要求。     

A parallel Ada system on an experimental multiprocessor

This paper describes the development of a parallel Ada system on an experimental MIMD multiprocessor. The system enables a single unmodified Ada program, with a number of tasks, to execute in parallel on different processors. Allocation and migration strategies are controlled by mechanisms in the run-time system, and are thus transparent to the Ada programmer. The parallel Ada system is based on a validated portable front-end compiler. Implementation issues related to the multiprocessor environment are pointed out, and solutions to these issues are suggested. The experimental multiprocessor environment, consisting of both hardware and software, is described. Applicable resource allocation strategies in, and feasible experiments with, the Ada system are discussed. The complete experimental system provides unique possibilities to experiment with, and monitor the effects of, design decisions at different levels in a multiprocessor environment.     

求解多处理机调度问题的蚁群算法

蚁群算法是受自然界中的蚂蚁觅食行为启发而设计的智能优化算法,特别适合处理离散型的组合优化问题。提出一种求解多处理机调度的蚁群算法,利用一个蚂蚁代表一个处理机来选择任务,并通过分析关键路径及每个任务的最早、最迟开始时间来确定每个任务的紧迫程度,让蚂蚁以此来选择任务。实验证明,该算法可比传统算法取得有更好运行效率的调度策略。     

多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

基于差分进化算法多处理机任务调度研究

本文主要基于现代启发式差分算法讨论多处理机调度,多处理机调度是NP组合优化问题,目前多采用启发算法。差分进化算法是最近提出的进化算法,主要根据父代个体之间矢量差构造下一代,是一种全局优化搜索方式。本文考虑采用差分进化矢量优先级模型描述调度顺序进行调度,与模拟退火算法比较得到较好调度结果。     

A framework using cluster-based hybrid network architecture for collaborative virtual surgery

Research on collaborative virtual environments (CVEs) opens the opportunity for simulating the cooperative work in surgical operations. It is however a challenging task to implement a high performance collaborative surgical simulation system because of the difficulty in maintaining state consistency with minimum network latencies, especially when sophisticated deformable models and haptics are involved. In this paper, an integrated framework using cluster-based hybrid network architecture is proposed to support collaborative virtual surgery. Multicast transmission is employed to transmit updated information among participants in order to reduce network latencies, while system consistency is maintained by an administrative server. Reliable multicast is implemented using distributed message acknowledgment based on cluster cooperation and sliding window technique. The robustness of the framework is guaranteed by the failure detection chain which enables smooth transition when participants join and leave the collaboration, including normal and involuntary leaving. Communication overhead is further reduced by implementing a number of management approaches such as computational policies and collaborative mechanisms. The feasibility of the proposed framework is demonstrated by successfully extending an existing standalone orthopedic surgery trainer into a collaborative simulation system. A series of experiments have been conducted to evaluate the system performance. The results demonstrate that the proposed framework is capable of supporting collaborative surgical simulation.     

多处理器固定优先级算法的可调度性分析

针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。     

Performance of symbolic applications on a parallel architecture

The results of a study of a family of parallel symbolic architectures executing several parallel applications are presented. The class of architectures being simulated is characterized by a shared memory structure, by a hierarchical interconnect, and by clustered processors. Speedup measurements were obtained from six different application kernels. Measurements were also performed to assess the degradation of speedup as a function of the interconnection delays, and to study the effect of different scheduling algorithms. The results presented support the claim that the proposed architecture would be a powerful parallel symbolic computation system. The paper discusses processor starvation, fine grain parallelism, unever loads, foreign reference, schedule and indeterminate computation with respect to the applications chosen.This work was completed within the Advanced Computer Architecture Program, Micro-electronics and Technology Computer Corporation, Austin, Texas.     

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。     

Parallel processing of incremental ray tracing on a shared-memory multiprocessor

This paper presents a novel parallel-processing method for image synthesis using incremental ray tracing on a shared-memory multiprocessor workstation. The most efficient technique for image synthesis is ray tracing, proposed by Whitted in 1980. Ray-tracing algorithms are simple and can generate realistic images. However, they are time-consuming, since calculations of the intersections between objects and ray increase exponentially as the complexity of scenes increases. Fast image synthesis for animation is one of the most important topics in computer graphics. As the area of computer applications has broadened, the complexity of images to be synthesized has increased. Parallel processing of computer graphics is one way of achieving fast image synthesis. This paper describes a parallel processing technique for incremental ray tracing, which recalculates only the rays changed by moving objects in successive scenes of continuous image synthesis. The performance of parallel ray tracing was evaluated on the multiprocessor workstation TOP-1. Strategies for allocating pixels to processes under a multiprocess operating system on this workstation are discussed.