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.     

i860XP多机并行系统的Cache一致性策略及其实现

本文讨论承公共总线和纵模交叉开关结构的ｉ８６０ＸＰ多机并行系统中Ｃａｃｈｅ一致性的实现策略。     

基于i860XP和Transputer的异构型多处理器系统

新出现的ＲＩＳＣ微处理器提供了超计算能力，采用ｉ８６０ＸＰ超标量微处理器来增强已存在Ｔｒａｎｓｐｕｔｅｒ系统的性能是一种切实可行的方法，它们构造了一种异构型多处理器系统，本文给出了该系统的设计和性能分析。     

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.     

多处理机并行计算自动测控系统

介绍了多处理机系统的并行计算,在此基础上,给出了采用十刻度策略解决任务排序,采用满射策略解决任务映射的算法。最后,给出了一个自动测控系统示例,该系统不仅可以使多台处理机同时进行多种不同仪器仪表、设备的测控工作,而且处理机间的通信成本较低,加快了被测对象的测试速度,节省了测试时间。     

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.     

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.     

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

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

Intel 8098／8051单片机的多机互连方案的研究

本文讨论了多单片机的几种互连方案，并针对８０９８／８０５１，利用本身的资源，设计了公共总线方案，对该方案的循环判优逻辑，同步机制，通信邮箱分配和时间指标等进行了详细的分析，为实际应用奠定了基础。     

一种基于C-PCI总线的HMCS地址映射机制研究

针对总线型计算机的主机风险与主机效率问题,提出了一种无主多处理器结构,以Intel-21554非透明桥为硬件基础,在这种结构中建立了处理器域之间的地址映射模型。这不但能够解决传统系统面临的根本问题,同时提供了灵活的系统级备份模式,具有最高处理器安装密度以及信息处理能力,系统的综合性能被最大化。     

可生存系统的分层冗余结构与实现

传统网络安全技术无法保证某些实时系统及统可生存能力方法的研究分析的基础上,提出了可生存系统的分层冗余结构模型.该模型在各个层次上引进异构组件及互监视机制,既可避免基于主动响应的可生存系统检测能力和响应速度的缺陷,又能解决基于同构冗余的可生存系统无法抵抗可重复攻击的问题.实践结果表明,与传统的可生存系统模型相比,提出的分层冗余结构在系统受到恶意攻击或系统部分组建受损的情况下仍能维持一定程度的工作并持续提供服务.     

Designing linear algebra algorithms on the IBM 3090 vector multiprocessor with a hierarchical memory system

The IBM 3090 is a vector multiprocessor with a hierarchical memory system. We show with two examples (the LU and Householder factorizations) that the complex memory system and the vector hardware can be used efficiently by recasting the basic algorithms in terms of high-level matrix-matrix modules.     

Solution of the neutron diffusion equation through multigrid methods implemented on a memory-coupled 25-processor system

For the complex task to attain maximum use and maximum security maintenance of nuclear reactors, we simulate the physical behaviour by way of mathematical models. The stationary solution of the Neutron Diffusion Equation as an eigenvalue problem, presented in this paper, results in a large non-linear partial differential equation system (PDE) whose solution is parallelized and implemented on the DIRMU multiprocessor system. We demonstrate that modern algorithms (e.g. multigrid methods) combined with innovative hardware (e.g. vector-multiprocessor systems) can lead to powerful tools which are needed for real-time simulation of physical events. This approach also allows to solve problems which arise in fluid dynamics, aerodynamics, weather forecast, etc. in a reasonable amount of time.     

多处理器系统可靠性约束下的节能调度算法

针对多处理器系统中随机到达的任务,设计了可靠性约束下的节能调度算法(ESACR)。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能,在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡,当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时,为保证系统的可靠性,ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明,与最高电压节能调度(HVEA)、最小能耗最小完成时间调度(ME-MC)、最早完成时间优先调度(EFF)相比,ESACR在保证系统可靠性的前提下节能效果最好。     

A softerware monitor for shared-memory multiprocessor computers

ANIX is a multiprocessor operating system to be used in the backbone Asynchronous Transfer Mode (ATM) switches. In ANIX, memory contention by processes running on different CPUs is managed with a protocol called WWWH (when to sleep, who to sleep, where to sleep, and how to sleep). Tools are needed to test, debug, and tune the system running WWWH. This paper describes the experience and practice in design of SHMON, a performance tool that monitors the dynamic behavior of the running system. Copyright © 2004 John Wiley & Sons, Ltd.     

一种多I860系统的设计与实现

本文介绍了Ｉ８６０ＸＰ微处理器及双Ｉ８６０ＸＰ系统，然后给出了一种多Ｉ８６０系统的设计与实现方案，并且分析了其性能指标。     

A space-efficient parallel sequence comparison algorithm for a message-passing multiprocessor

We present a parallel algorithm for computing an optimal sequence alignment in efficient space. The algorithm is intended for a message-passing architecture with one-dimensional-array topology. The algorithm computes an optimal alignment of two sequences of lengthsM andN inO((M+N) ² /P) time andO((M+N)/P) space per processor, where the number of processors isP>=max(M, N). Thus, whenP=max(M, N) it achieves linear speedup and requires constant space per processor. Some experimental results on an Intel hypercube are provided.This research was supported by NIH Grant LM05110 from the National Library of Medicine.     

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.     

一种基于异构双核处理器的嵌入式操作系统构架设计

当前应用于异构多核处理器嵌入式操作系统主要是主从式结构。这种结构由于存在通信协议和结构的异构性,使操作系统在实现上和通信处理存在复杂性。根据异构双核处理器的特点,通过分析通信硬件的结构,在单核嵌入式操作系统构架的基础上,提出一种基于对称通信的双核处理器嵌入式操作系统构架,解决了异构双核处理器中的通信效率和共享内存的利用问题。该操作系统构架成功应用于TI OMAP5910处理器。