An appropriate automatic thread decomposition approach is critical for pipelined multithreading (PMT) to maximize pipeline performance with balanced thread size on target multi-core processor. This paper presents an automatic thread decomposition approach, which maps the pipeline thread decomposition problem onto a graph-theoretic framework to construct an optimized DAG with minimal bottleneck node size and balanced node size under constrained core number. In this approach, control dependence is treated as special data dependence and then an effective mechanism is proposed to remove redundant control dependences. A heuristic decomposition algorithm is given to generate an optimized pipeline. The algorithm has been evaluated on a commodity multi-core processor, and experimental results show that it has achieved speedup ranging from 113% to 174% on several SPEC CPU 2000 benchmark programs.

Multi-core processors have emerged as predominant architecture. Parallelizing applications into multithreaded ones executing on multiple cores is the key to achieving performance improvements. Recently proposed pipelined multithreading (PMT) techniques have shown great promise to parallelizing general applications. However, significant inter-core communication overheads limit the potential performance and hinder the wide commercial use. While dedicated inter-core communication mechanism has been proposed, it demands chip redesign effort, costs so much and needs extensions to ISA. Software queues avoid these problems. In this paper, we propose a clustered software queue technique, which applies a new clustered communication mechanism, to minimize the communication overheads from the average standpoint. Our research shows that very low average communication overheads (ACOs) can be achieved by sacrificing a certain amount of parallelisms. The principle of clustered communication mechanism and how to reduce the ACOs with it are presented in detail. A concurrent lock-free clustered software queue algorithm is given and then evaluated on commodity multi-core processors. Experimental results show that the communication performance of clustered software queue is over 10x faster than that of conventional software queue, and much higher PMT performances of real applications are achieved.

With the prevalence of chip multiprocessor (CMP) on server and client computers, it becomes an important issue to use the multicores to speedup existing sequential programs. Decoupled software pipelining (DSWP) is a recent proposed technique that extracts non-speculative threads from sequential programs for higher performance. However, this technique is not effective on commodity CMP architecture, because the inter-thread communication and synchronization overhead often offset the benefit from the parallelization. To reduce the overhead without modification to CMP architecture, this paper presents a clustered DSWP (CDSWP) technique that is an extension to DSWP. By communicating a dependent data set instead of a single dependent data, this technique transforms sequential program into a clustered thread pipeline. The meaning of "clustered" is that some dependent data items are clustered together as a communication unit. The advantage of this technique is that it can eliminate false sharing and reduce the average cache latency, and thus the overhead is reduced greatly. According to the preliminary experiments on some commodity CMP architectures, we have achieved loop speedup ranging from 16% to 58% on some SPEC2000 benchmark programs.

Parallel computers essentially employ interconnection networks. Huge-scale systems require appropriate networks that can correspond to their required performance. This paper addresses a scalability issue of uniform interconnection networks. We first propose an evaluation method suitable to large-scale networks, define critical load ratio as a common measure, and introduce introduce ramp-, step-, and impulse responses. Our evaluation results reveal some new knowledge on large-scale networks: (1) performance is scalable from macro-scopic viewpoint, (2) large-scale network is sensitive to congestion and sometimes complex behaviors emerge.

Extracting thread-level parallelism, as well as instruction-level one, is greatly expected for modern microprocessors. Speculative multithreading is one of the most hopeful candidates, although, its performance improvement depends on prediction accuracy. On the other hand, profiling techniques can accelerate programs since it can reflect the programs’ actual behavior. This paper focuses our discussion on utilizing path-based profiling results in improving speculative multithreaded codes. Programs have many conditional branches thus many possible paths arise, however, actually executed paths are very limited. Thus we show that most frequent two paths are sufficient candidates for prediction and speculation, and we present a novel speculation method, two-path limited speculation. Furthermore, we present a simple path predictor based on two level branch predictor. Analytical and trace-driven evaluation results show the effectiveness of the proposed method.

Concentration index filter is a kind of spatial filters of images, and its typical application is diagnosis from medical images. This paper presents a dedicated computing engine for concentration index filtering. Original algorithm is modified to extract full parallelism and data width is optimized for maximizing clock speed and minimizing hardware scale. Evaluation results reveal that the system runs 100 times faster than current workstation and enables real-time diagnosis.

Thread Level Parallelism (TLP) is the most promising way to the futur e high-p erformance microprocessors. When a sequential program code is speculatively execute din a multithreaded manner, it is natural that each speculative thread follows the control ow of the program. Based on this backgr ound, various studies have b en performed on speculative multithreading, following control ow graph. This pap erprop osesa new execution model that aims at the speedup of the execution of usual sequential program codes by sp eculatively executing the multiple contr ol ows in parallel. Further, this paper shows the thread contr olmechanism and the inter-thread communication facility requir ed for the realization of the model. F or the evaluation of our model, the cycle-b asedinstruction-level simulator has been developed. We evaluate our model with simple benchmark programs and show the e ectiveness of our model especially, for the case where the speculation by single c ontr ol ow is di cult to sp eedup the programs.

In order to improve network performance, a variety of adaptive routing algorithms have been proposed. Recent research focuses on their implementation costs, as well as the performance to enhance their practical applications. The paper proposes the Recover-x adaptive router, which limits escape message candidate in a blocked or deadlocked configuration. This limitation simplifies the routing logic and offers a chance to balance the usage between adaptive and non-adaptive channels. The cost and performance of four wormhole routers based on Verilog-HDL designs were compared. Synthesis results for the chosen gate array technology show that the Recover-x router attains a fast operating speed and low-latency, with high-bandwidth communication performance.

Our research investigates cost and performance characteristics for wormhole routers based on HDL designs. Comparison for dimension order routers and turn model based adaptive routers leads to the following conclusions: (1) static and additional routing information which we propose, such as prior dimension specification and in-order delivery, improves the communication performance; (2) an adaptive routing algorithm must be implemented to satisfy the objective speed of the design (the operation speed of the routers significantly affects the network performance); (3) the virtual channels cancel the improvement not only for the dimension order router but also for the naive implementation of the adaptive routers when they degrade the operation speed.

The paper proposes the realization of evolutionary computation on an intelligent agent using knowledge creation based on chaotic retrieval and parallel processing. This intelligent agent has the ability to self-organize knowledge, and the authors intend to introduce a kind of evolutionary computation into intelligent agents to make use of the flexibility in a group of various agents. This agent model consists of hierarchical parts which memorize fuzzy knowledge. Each hierarchical part retrieves the knowledge based on fuzzy associative inference on associative memories. Essentially, this inference in each part is parallel processing, and these hierarchical parts also work in parallel. Furthermore, a large number of agents work in parallel on the multi-agent model and its evolutionary computation. They realize parallel processing according to these parallel properties in the brain and in nature. When they realize a welfare intelligent robot, robots have to move in a suitable formation, in cooperation with the outer environment. Therefore, they apply the knowledge creation method to multi-agent robots which move abreast and simulate parallel processing of the multi-agent model as the basis for realizing evolutionary computation. They implement a parallel processing algorithm on an A-NET (Actors NETwork) parallel object-oriented computer, and show the usefulness of parallel processing for future evolutionary computation.

A description is presented of the design principles and features of the A-NETL, a language for describing highly parallel programs. The authors explain the features by using an example program. They also refer to its programming environment, which includes a multiwindow-based programming support system, language processors, and a debugger.>

For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties of the graphs. Several strategies are defined to guide the mapping process, utilizing the indicated values. An allocation system has been designed and implemented based on this strategy. The experimental results indicate the following: the system can yield 2.14 times better allocation than an arbitrary allocation; it is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations; and the computation time of the allocator is reasonable. The effect of task and processor topology combinations on the allocation results is also discussed.>

A-NET is a parallel object-oriented total architecture for highly parallel computation. Starting with a computation model, the authors describe parallel constructs of the designed language, called A-NETL; the A-NETL-oriented machine instruction set architecture; the hardware organization of a node processor, which consists of a 40-bit processing element and a router; and a local operating system on each of the node processors. Statistics for the designed language and the machine are derived from experimental results.>

We propose a design methodology based on data flow analysis for a functionally distributed, multiprocessor database machine. We define a cost model of database processing with the objective cost being response time of a set of query strategies. Heuristic optimization techniques are proposed using the operations of grouping, decomposition, and replication. We apply the new optimization techniques in several realistic multiprocessor environments. The resulting configurations of multiprocessors demonstrate significant performance improvements over more traditional designs.

A two-level microprogrammed multiprocessor system, MUNAP, along with its support software has been developed as a research vehicle for solving nonnumeric and associated problems. The MUNAP system provides highly parallel and distributed functions for nonnumeric processing, such as variable length word addressing, data permutation at the microprogram level, and bit operation and field handling at the multinanoprogram level. To control these functions efficiently, a 28-bit microinstruction simultaneously drives several nanoprogram streams of 40-bit nanoinstructions in the four 16-bit processor units. This scheme not only provides the ability to organize a number of modular processing elements into a single, parallel processable computer system, but also allows MUNAP to change its architecture at the firmware level.

A machine-independent high-level microprogramming language, called MPGL, has been developed along with its processing system, called MPG. The MPGL allows the microprogrammer to write microprograms sequentially in a machine-independent fashion. The MPG provides the facility for translating these microprograms into efficient object code, as well as debugging object microprograms.