多处理器芯片体系结构研究

随着超大规模集成电路工艺和超级计算技术的发展，作者认为在单个芯片内集成多处理器系统将成为可能。本文详细讨论了多处理器芯片的分类和结构，着重阐述了同构型多处理器芯片的主要研究方向，并对同构型多处理器的可行性作出了分析。     

用Boltzmann网络解任务安排问题

本文提出了一种解任务安排问题的Ｂｏｌｔｚｍａｎｎ网络算法，已在Ｔｒａｎｓｐｕｔｅｒ多处理机系统上并行模拟实现，该算法具有优化程度高，运算速度快等特点．     

Longest fault-free paths in hypercubes with vertex faults

The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2ⁿ − 2f − 1 (or 2ⁿ − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal.     

Fault tolerance in multiprocessor systems

Multiprocessor systems which afford a high degree of parallelism are used in a variety of applications. The extremely stringent reliability requirement has made the provision of fault-tolerance an important aspect in the design of such systems. This paper presents a review of the various approaches towards tolerating hardware faults in multiprocessor systems. It emphasizes the basic concepts of fault tolerant design and the various problems to be taken care of by the designer. An indepth survey of the various models, techniques and methods for fault diagnosis is given. Further, we consider the strategies for fault-tolerance in specialized multiprocessor architectures which have the ability of dynamic reconfiguration and are suited tovlsi implementation. An analysis of the state-of-the-art is given which points out the major aspects of fault-tolerance in such architectures.     

Unified reliability estimation and management of NoC based chip multiprocessors

We present a new architecture level unified reliability evaluation methodology for chip multiprocessors (CMPs). The proposed reliability estimation (REST) is based on a Monte Carlo algorithm. What distinguishes REST from the previous work is that both the computational and communication components are considered in a unified manner to compute the reliability of the CMP. We utilize REST tool to develop a new dynamic reliability management (DRM) scheme to address time-dependent dielectric breakdown and negative-bias temperature instability aging mechanisms in network-on-chip (NoC) based CMPs. Designed as a control loop, the proposed DRM scheme uses an effective neural network based reliability estimation module. The neural-network predictor is trained using the REST tool. We investigate how system’s lifetime changes when the NoC as the communication unit of the CMP is considered or not during the reliability evaluation process and find that differences can be as high as 60%. Full-system based simulations using a customized GEM5 simulator show that reliability can be improved by up to 52% using the proposed DRM scheme in a best-effort scenario with 2–9% performance penalty (using a user set target lifetime of 7 years) over the case when no DRM is employed.     

A new parallel lattice reduction algorithm for BKZ reduced bases

In order to implement the original BKZ algorithm in parallel,we describe it in terms of parallelism and give its parallel implementation scheme.Then we analyze the efficiency of algorithm’s parallel implementation and show that the speedup factor of BKZ algorithm in parallel is extremely low.Therefore we present a new parallel lattice reduction algorithm suitable for multiprocessor computer architecture.The new algorithm can obtain a BKZ reduced basis and the parallel speedup is effective.Also with the practical results,although the computational complexity increases compared with the original BKZ algorithm,we still indicate that the new algorithm performs well in parallel and the time cost in parallel is less.At the same time,we show that the length of the shortest vector is smaller.     

多选择软硬件划分问题的计算模型与动态规划算法

软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。     

Path partitions of hypercubes

A path partition of a graph G is a set of vertex-disjoint paths that cover all vertices of G. Given a set of pairs of distinct vertices of the n-dimensional hypercube Qn, is there a path partition of Qn such that ai and bi are endvertices of Pi? Caha and Koubek showed that for 6m?n, such a path partition exists if and only if the set P is balanced in the sense that it contains the same number of vertices from both classes of bipartition of Qn.In this paper we show that this result holds even for 2m−e<n, where e is the number of pairs of P that form edges of Qn. Moreover, our bound is optimal in the sense that for every n?3, there is a balanced set P in Qn such that 2m−e=n, but no path partition with endvertices prescribed by P exists.     

片上多核处理器容软错误执行模型

随着工艺的进步,微处理器将面临越来越严重的软错误威胁.文中提出了两种片上多核处理器容软错误执行模型:双核冗余执行模型DCR和三核冗余执行模型TCR.DCR在两个冗余的内核上以一定的时间间距运行两份相同的线程,store指令只有在进行了结果比较以后才能提交.每个内核增加了硬件实现的现场保存与恢复机制,以实现对软错误的恢复.文中选择的现场保存点有利于隐藏现场保存带来的时间开销,并且采用了特殊的机制保证恢复执行和原始执行过程中load数据的一致性.TCR执行模型通过在3个不同的内核上运行相同的线程实现对软错误的屏蔽.在检测到软错误以后,TCR可以进行动态重构,屏蔽被软错误破坏的内核.实验结果表明,与传统的软错误恢复执行模型CRTR相比,DCR和TCR对核间通信带宽的需求分别降低了57.5%和54.2%.在检测到软错误的情况下,DCR的恢复执行带来5.2%的性能开销,而TCR的重构带来的性能开销为1.3%.错误注入实验表明,DCR能够恢复99.69%的软错误,而TCR实现了对SEU(Single Event Upset)型故障的全面屏蔽.     

A multiperiod set covering location model for dynamic redeployment of ambulances

Emergency medical service (EMS) providers continually seek ways to improve system performance particularly the response time to incidents. The demand for ambulances fluctuate throughout the week, depending on the day of week, and even the time of day, therefore EMS operators can improve system performance by dynamic relocation/redeployment of ambulances in response to fluctuating demand patters. The objective of the model is to determine the minimum number of ambulances and their locations for each time cluster in which significant changes in demand pattern occur while meeting coverage requirement with a predetermined reliability. The model is further enhanced by calculating ambulance specific busy probabilities and validated by a comprehensive simulation model. Computational results on experimental data sets and data from an EMS agency are provided.