Adaptive Online Voltage Scaling Scheme Based on the Nash Bargaining Solution

In an effort to reduce energy consumption, research into adaptive power management in real‐time systems has become widespread. In this paper, a novel dynamic voltage scaling scheme is proposed for multiprocessor systems. Based on the concept of the Nash bargaining solution, a processor's clock speed and supply voltage are dynamically adjusted to satisfy these conflicting performance metrics. In addition, the proposed algorithm is implemented to react adaptively to the current system conditions by using an adaptive online approach. Simulation results clearly indicate that the superior performance of the proposed scheme can strike the appropriate performance balance between contradictory requirements.     

Multi-objective two-stage multiprocessor flow shop scheduling – a subgroup particle swarm optimisation approach

Flow shop production system – compared to other economically important production systems – is popular in real manufacturing environments. This study focuses on the flow shop with multiprocessor scheduling problem (FSMP), and develops an improved particle swarm optimisation heuristic to solve it. Additionally, this study designs an integer programming model to perform effectiveness and robustness testing on the proposed heuristic. Experimental results demonstrate a 10% to 50% improvement in the effectiveness of the proposed heuristic in small-scale problem tests, and a 10% to 40% improvement in the robustness of the heuristic in large-scale problem tests, indicating extremely satisfactory performance.     

On an efficient NoC multicasting scheme in support of multiple applications running on irregular sub-networks

When a number of applications simultaneously running on a many-core chip multiprocessor (CMP) chip connected through network-on-chip (NoC), significant amount of on-chip traffic is one-to-many (multicast) in nature. As a matter of fact, when multiple applications are mapped onto an NoC architecture with applicable traffic isolation constraints, the corresponding sub-networks of these applications are mapped onto actually tend to be irregular. In the literature, multicasting for irregular topologies is supported through either multiple unicasting or broadcasting, which, unfortunately, results in overly high power consumption and/or long network latency. To address this problem, a simple, yet efficient hardware-based multicasting scheme is proposed in this paper. First, an irregular oriented multicast strategy is proposed. Literally, following this strategy, an irregular oriented multicast routing algorithm can be designed based on any regular mesh based multicast routing algorithm. One such algorithm, namely, Alternative Recursive Partitioning Multicasting (AL + RPM), is proposed based on RPM, which was designed for regular mesh topology originally. The basic idea of AL + RPM is to find the output directions following the basic RPM algorithm and then decide to replicate the packets to the original output directions or the alternative (AL) output directions based on the shape of the sub-network. The experiment results show that the proposed multicast AL + RPM algorithm can consume, on average, 14% and 20% less power than bLBDR (a broadcasting-based routing algorithm) and the multiple unicast scheme, respectively. In addition, AL + RPM has much lower network latency than the above two approaches. To incorporate AL + RPM into a baseline router to support multicasting, the area overhead is fairly modest, less than 5.5%.     

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.     

Locality Aware Optimal Task Scheduling Algorithm for TriBA——A Novel Scalable Architecture

An optimal algorithmic approach to task scheduling for, triplet based architecture（TriBA）, is proposed in this paper. TriBA is considered to be a high performance, distributed parallel computing architecture. TriBA consists of a 2D grid of small, programmable processing units, each physically connected to its three neighbors. In parallel or distributed environment an efficient assignment of tasks to the processing elements is imperative to achieve fast job turnaround time. Moreover, the sojourn time experienced by each individual job should be minimized. The arriving jobs are comprised of parallel applications, each consisting of multiple-independent tasks that must be instantaneously assigned to processor queues, as they arrive. The processors independently and concurrently service these tasks. The key scheduling issues is, when some queue backlogs are small, an incoming job should first spread its tasks to those lightly loaded queues in order to take advantage of the parallel processing gain. Our algorithmic approach achieves optimality in task scheduling by assigning consecutive tasks to a triplet of processors exploiting locality in tasks. The experimental results show that tasks allocation to triplets of processing elements is efficient and optimal. Comparison to well accepted interconnection strategy, 2D mesh, is shown to prove the effectiveness of our algorithmic approach for TriBA. Finally we conclude that TriBA can be an efficient interconnection strategy for computations intensive applications, if tasks assignment is carried out optimally using algorithmic approach.     

Performance analysis of a separate address/data bus multiprocessor system

Abstract

This paper presents a performance model of a special shared bus multiprocessor system, that features: (1) separate address‐bus and data‐bus with split transaction, pipelined cycle; (2) two‐level cache structure; and (3) multiple main memory and I/O modules. Accessing conflicts in these subsystems, maintaining shared data and DMA transfer between memory and I/O subsystems are also considered in the model. The representation for the complex behavior of a whole multiprocessor system distinguishes the model from others that present only one major subsystem. The performance model can be used not only to assist in evaluating the architectural design of aparticular system, but also directly utilized to identify subsystem bottlenecks and their causes in order to make performance improvements. Results show that: (1) the values of some key design parameters, such as cache line size and data‐bus width that yield the best throughput, are dependent on the performance of subsystems; (2) choosing the data‐bus width at one‐half of cache line size can achieve the lowest access time in the shared bus; (3) using cache‐to‐cache transfer protocol may prevent performance degradation caused by maintaining shared data; and (4) the activity of DMA transfer may significantly affect system throughput and should be included in a performance model of multiprocessor systems.     

Problem size scaling in the presence of parallel overhead

In this paper we study the performance of applications on multiprocessor systems. In particular we investigate the effect of synchronization and parallelization overhead where the fact that part of the application may be inherently sequential is taken into account. By relating our assumptions to an earlier work by Flatt and Kennedy we establish that the overhead function can be characterized using the concept of convex functions. In order to observe a satisfactory payoff for increased processing power it is essential to increase the problem size accordingly. We discuss linear and nonlinear scaling schemes and compare the corresponding asymptotic performance behaviour. Throughout this investigation we profit from the well developed mathematical apparatus of convex functions.     

Mesh-connected parallel computer PAX for scientific applications

Nearest-neighbor-mesh connection plus global broadcasting/control bus characterizes the architecture of the processor array PAX, that was constructed for and is now operating in many typical scientific applications. Not only these inter-processor connections, but also an MIMD structure of the machine were found effective in the particle transport problems, that require asynchronous operation.

The paper describes the bases of architecture of two recent versions of the PAX computer, their hardware and software systems, and, based on the implementation of scientific applications, the effectiveness of the PAX type architecture is presented.     

A streams-based communications subsystem in turing plus for protocol development

The Homogeneous Multiprocessor (HM) has a linear-array topology, with interprocessor communications achieved by the sharing of memory between nearest neighbours, by adjacent-processor signalling, and through a high-speed network (the H-Network). The operating system nucleus (the HM-Nucleus) for the HM contains a communications subsystem that provides low-overhead communications, both for user processes and for the rest of the HM-Nucleus, using the shared memory, the signalling capability, and the H-Network. The design for the communications subsystem provides uniformity of access to the three mechanisms by following the IEEE 802.2/802.3 LLC/MAC specifications. Flexibility of access is achieved by adopting the STREAMS facility from System V UNIX. A new implementation of STREAMS has been built using Turing Plus for both the programming and the simulation/testing, with no need to access the actual hardware until final test. Completion of the STREAMS framework has made it possible subsequently to code an 802.2 LLC module and an 802.3-based shared memory driver very quickly. The STREAMS framework has also made it feasible to cast some algorithms used by other parts of the HM-Nucleus as protocols, and implement them as STREAMS modules, resulting in considerable simplification in the design process. Since the framework was designed to be completely independent of the host processor, it provides a very general vehicle for protocol development.     

Scattering on a ring of processors

In this note, we prove that the complexity of scattering in an oriented ring of p processors is (p - 1) (β + Lτ) where L is the length of the messages, β the communication startup, and τ the elemental propagation time.