8533475
Parallelization of DOALL and DOACROSS Loops - A Survey
Abstract Since loops in programs are the major source of parallelism, considerable research has been focused on strategies for parallelizing loops. For DOALL loops, loops can be allocated to processors either statically or dynamically. When the execution times of individual iterations vary, dynamic schemes can achieve better load balance, albeit at a higher runtime scheduling cost. The inter-iteration dependencies of DOACROSS loops can be constant (regular DOACROSS loops) or variable (irregular DOACROSS loops). In our research, we have proposed and tested two loop allocation techniques for regular DOACROSS loops, known as Staggered distribution (SD) and Cyclic Staggered (CSD) distribution. This article analyzes several classes of loop allocation algorithms for parallelizing DOALL, regular, and irregular DOACROSS loops.
18416128
Dynamic Simultaneous Multithreaded Architecture
This paper presents the Dynamic Simultaneous Multithreaded Architecture (DSMT). DSMT efficiently executes multiple threads from a single program on a SMT processor core. To accomplish this, threads are generated dynamically from a predictable flow of control and then executed speculatively. Data obtained during the single context nonspeculative execution phase of DSMT is used as a hint to speculate the posterior behavior of multiple threads. DSMT employs simple mechanisms based on state bits that keep track of inter-thread dependencies in registers and memory, synchronize thread execution, and control recovery from misspeculation. Moreover, DSMT utilizes a novel greedy policy for choosing those sections of code which provide the highest performance based on their past execution history. The DSMT architecture was simulated with a new cycle-accurate, execution-driven simulator. Our simulation results show that DSMT has very good potential to improve SMT performance, even when only a single program is available. However, we found that dynamic thread behavior together with frequent misspeculation may also produce diminishing returns in performance. Therefore, the challenge is to maximize the amount of thread-level parallelism that DSMT is capable of exploiting and at the same time reduce the frequency of misspeculations.
11122198
Shared memory and distributed shared memory systems: A survey
Publisher Summary This chapter illustrates distributed shared memory (DSM) systems that are intended to combine the ease of programming of the shared-memory model with the scalability of the distributed-memory system. DSM systems aim to unify parallel processing systems that rely on message passing with the shared-memory systems. The chapter explores the design space for such systems and includes descriptions of both hardware- and software-supported DSM systems. The implementation prototypes of some of the systems are based on older technology and older software designs, making them appear to perform poorly.
6217758
Implementation and Performance Evaluation of M-VIA on AceNIC Gigabit Ethernet Card
This paper describes the implementation and performance of M-VIA on the AceNIC Gigabit Ethernet card. The AceNIC adapter has several notable hardware features for high-speed communication, such as jumbo frames and interrupt coalescing. The M-VIA performance charac- teristics were measured and evaluated based on these hardware features. Our results show that latency and bandwidth improvement can be ob- tained when the M-VIA data segmentation size is properly adjusted to utilize the AceNIC's jumbo frame feature. The M-VIA data segmenta- tion size of 4,096 bytes with MTU size of 4,138 bytes showed the best performance. However, larger MTU sizes did not necessarily result in better performance due to extra segmentation and DMA setup over- head. In addition, the cost of M-VIA interrupt handling can be reduced with AceNIC's hardware interrupt coalescing. When the parameters for the hardware interrupt coalescing were properly adjusted, the latency of interrupt handling was reduced by up to 170 µs.
1642899
Isomorphic Strategy for Processor Allocation in k-Ary n-Cube Systems
Due to its topological generality and flexibility, the k-ary n-cube architecture has been actively researched for various applications. However, the processor allocation problem has not been adequately addressed for the k-ary n-cube architecture, even though it has been studied extensively for hypercubes and meshes. The earlier k-ary n-cube allocation schemes based on conventional slice partitioning suffer from internal fragmentation of processors. In contrast, algorithms based on job-based partitioning alleviate the fragmentation problem but require higher time complexity. This paper proposes a new allocation scheme based on isomorphic partitioning, where the processor space is partitioned into higher dimensional isomorphic subcubes. The proposed scheme minimizes the fragmentation problem and is general in the sense that any size request can be supported and the host architecture need not be isomorphic. Extensive simulation study reveals that the proposed scheme significantly outperforms earlier schemes in terms of mean response time for practical size k-ary and n-cube architectures. The simulation results also show that reduction of external fragmentation is more substantial than internal fragmentation with the proposed scheme.
7462465
Power Analysis and Optimization Techniques for Energy Efficient Computer Systems
Reducing power consumption has become a major challenge in the design and operation of today's computer systems. This chapter describes different techniques addressing this challenge at different levels of system hardware, such as CPU, memory, and internal interconnection network, as well as at different levels of software components, such as compiler, operating system and user applications. These techniques can be broadly categorized into two types: Design time power analysis versus run-time dynamic power management. Mechanisms in the first category use analytical energy models that are integrated into existing simulators to measure the system's power consumption and thus help engineers to test power-conscious hardware and software during design time. On the other hand, dynamic power management techniques are applied during run-time, and are used to monitor system workload and adapt the system's behavior dynamically to save energy.
2176970
Implications of programmable general purpose processors for compression/encryption applications
With the growth of the Internet and mobile communication industry, multimedia applications form a dominant computer workload. Media workloads are typically executed on Application Specific Integrated Circuits (ASICs), application specific processors (ASPs) or general purpose processors (GPPs). GPPs are flexible and allow changes in the applications and algorithms better than ASICs and ASPs. However, executing these applications on GPPs is done at a high cost. In this paper, we analyze media compression/decompression algorithms from the perspective of the overhead of executing them on a programmable general purpose processor versus ASPs. We choose nine encode/decode programs from audio, image/video andencryption applications. The instruction mix, memory access and parallelism aspects during the execution of these programs are analyzed. Memory access latency is observed to be the main factor influencing the execution time on general purpose processors. Most of these compression/decompression algorithms involve processing the data through execution phases (e.g. quantization, encoding, etc) and temporary results are stored and retrieved between these phases. A metric called overhead memory-access bandwidth per input/output byte is defined to characterize the temporary memory activity of each application. We observe that more than 90% of the memory accesses made by these programs are temporary data stores and loads arising from the general purpose nature of the execution platform. We also study the data parallelism in these applications, indicating the ability of instruction level and data level parallel processors to exploit the parallelism in these applications. The parallelism ranges from 6 to 529 in encode processes and 18 to 558 in decode processes.
7685565
TWIMC: An Anonymous Recipient E-mail System
More and more people rely on e-mails rather than postal letters to communicate each other. Although e-mails are more convenient, letters still have many nice features. The ability to handle "anonymous recipient" is one of them. This research aims to develop a software agent that performs the routing task as human beings for the anonymous recipient e-mails. The software agent named "TWIMC (To Whom It May Concern)" receives anonymous recipient e-mails, analyze it, and then routes the e-mail to the mostly qualified person (i.e., e-mail account) inside the organization. The machine learning and automatic text categorization (ATC) techniques are applied for the task. We view each e-mail account as a category (or class) of ATC. Everyday e-mail collections for each e-mail account provide an excellent source of training data. The experiment shows the high possibility that TWIMC could be deployed in the real world.
17892684
Refined statistical static timing analysis through
Statistical static timing analysis (SSTA) has been a popular research topic in recent years. A fundamental issue with applying SSTA in practice today is the lack of reliable and efficient statistical timing models (STM). Among many types of parameters required to be carefully modeled in an STM, spatial delay correlations are recognized as having significant impact on SSTA results. In this work, we assume that exact modeling of spatial delay correlations is quite difficult, and propose an experimental methodology to resolve this issue. The modeling accuracy requirement is relaxed by allowing SSTA to impose upper bounds and lower bounds on the delay correlations. These bounds can then be refined through learning the actual delay correlations from path delay testing on silicon. We utilize SSTA as the platform for learning and propose a Bayesian approach for learning spatial delay correlations. The effectiveness of the proposed methodology is illustrated through experiments on benchmark circuits.
8642618
Stationary subdivision schemes reproducing polynomials
A new class of subdivision schemes is presented. Each scheme in this class is a quasi-interpolatory scheme with a tension parameter, which reproduces polynomials up to a certain degree. We find that these schemes extend and unify not only the well-known Deslauriers-Dubuc interpolatory schemes but the quadratic and cubic B-spline schemes. This paper analyzes their convergence, smoothness and accuracy. It is proved that the proposed schemes provide at least the same or better smoothness and accuracy than the aforementioned schemes, when all the schemes are based on the same polynomial space. We also observe with some numerical examples that, by choosing an appropriate tension parameter, our new scheme can remove undesirable artifacts which usually appear in interpolatory schemes with irregularly distributed control points.
13888487
Hierarchical finite state machines with multiple concurrency models
This paper studies the semantics of hierarchical finite state machines (FSM's) that are composed using various concurrency models, particularly dataflow, discrete-events, and synchronous/reactive modeling. It is argued that all three combinations are useful, and that the concurrency model can be selected independently of the decision to use hierarchical FSM's. In contrast, most formalisms that combine FSM's with concurrency models, such as statecharts (and its variants) and hybrid systems, tightly integrate the FSM semantics with the concurrency semantics. An implementation that supports three combinations is described.