In the era of mobile and cloud computing, cross-ISA (Instruction Set Architecture) binary translation attracts increasing attentions due to the ISA diversity of computing platforms. To easily adapt to vast guest- and host-ISAs with minimal porting efforts, existing cross-ISA binary translators (e.g., QEMU) are typically built upon ISA-independent Intermediate Representation (IR). Although IR conceals the architectural details of different IS As, it also prevents enforcing several effective ISA-specific optimizations, which results in severe performance degradation. To improve the performance of cross-ISA binary translation without loss of portability, we present a fast cross-ISA binary translator, Hermes, by conducting post-optimization on the translated code, rather than on the IR as conventional binary translators do. The proposed post-optimization technique uses Host-specific Data Dependence Graph (HDDG) to significantly eliminate redundant instructions, including arithmetic, load/store and call/return-emulation instructions. To validate our approach, we implement Hermes on a commercial MIPS host system for both ×86 and ARM guest. Compared with QEMU dynamic binary translator, HERMES improves the performance by a factor of 3.14× and 5.18× for ×86 and ARM guest, respectively. Compared with state-of-the-art static binary translator, HERMES achieves comparable performance, while it reduces the translation overhead by 185×.

The ever-intensifying time-to-market pressure imposes great challenges on the pre-silicon design phase of hardware. Before the tape-out, a pre-silicon design has to be thoroughly inspected by time-consuming functional verification and code review to exclude bugs. For functional verification and code review, a critical issue determining their efficiency is the allocation of resources (e.g., computational resources and manpower) to different modules of a design, which is conventionally guided by designers' experiences. Such practices, though simple and straightforward, may take high risks of wasting resources on bug-free modules or missing bugs in buggy modules, and thus could affect the success and timeline of the tape-out. In this paper, we propose a novel framework called pre-silicon bug forecast to predict the bug information of hardware designs. In this framework, bug models are built via machine learning techniques to characterize the relationship between design characteristics and the bug information, which can be leveraged to predict how bugs distribute in different modules of the current design. Such predicted bug information is adequate to regulate the resources among different modules to achieve efficient functional verification and code review. To evaluate the effectiveness of the proposed pre-silicon bug forecast framework, we conducted detailed experiments on several open-source hardware projects. Moreover, we also investigate the impacts of different learning techniques and different sets of characteristic on the performance of bug models. Experimental results show that with appropriate learning techniques and characteristics, about 90% modules could be correctly predicted as buggy or clean and the number of bugs of each module could also be accurately predicted.

Debugging parallel programs is a well-known difficult problem. A promising method to facilitate debugging parallel programs is using hardware support to achieve deterministic replay on a Chip Multi-Processor (CMP). As a Design-For-Debug (DFD) feature, a practical hardware-assisted deterministic replay scheme should have low design and verification costs, as well as a small log size. To achieve these goals, we propose a novel and succinct hardware-assisted deterministic replay scheme named LReplay. The key innovation of LReplay is that instead of recording the logical time orders between instructions or instruction blocks as previous investigations, LReplay is built upon recording the pending period information infused by the global clock. By the recorded pending period information, about 99% execution orders are inferrable, implying that LReplay only needs to record directly the residual 1% noninferrable execution orders in production run. The 1% noninferrable orders can be addressed by a simple yet cost-effective direction prediction technique, which further reduces the log size of LReplay. Benefiting from the preceding innovations, the overall log size of LReplay over SPLASH-2 benchmarks is about 0.17B/K-Inst (byte per k-instruction) for the sequential consistency, and 0.57B/K-Inst for the Godson-3 consistency. Such log sizes are smaller in an order of magnitude than previous deterministic replay schemes incurring no performance loss. Furthermore, LReplay only consumes about 0.5% area of the Godson-3 CMP, since it requires only trivial modifications to existing components of Godson-3. The features of LReplay demonstrate the potential of integrating hardware support for deterministic replay into future industrial processors.

To efficiently and effectively debug silicon bugs, a promising solution is to determinize the chip, so that the buggy silicon behaviors can be faithfully reproduced on a RTL simulator. In this paper, we propose a novel scheme, named LDet, to determinize a chip through removing the nondeterminism in transfers crossing different clock domains, even when these clock domains are heterochronous. The key insight of LDet is that we can slightly adjust the frequencies of clocks at runtime so that the actual frequency ratio between two clocks always approaches a rational constant with bounded accumulated error. With the technique called dynamic frequency adjusting, the processing time of each asynchronous transfer can be determinized with deterministic asynchronous fifo (DAF). As a consequence, the behavior of the whole chip is deterministic, thus the chip behavior can be reproduced on the RTL simulator (given the same initial state and input sequence). We implement LDet on the RTL design of a processor chip with many clock domains. Experiments show that on average, LDet only causes about one cycle of additional latency to each asynchronous transfer. As a result, LDet only incurs a negligible performance overhead of about 0.7 percent slowdown. Moreover, LDet only brings less than 0.2 percent additional area to the chip. The low performance and area overheads of LDet well demonstrate its applicability in industry.

As a fundamental task in computer architecture research, performance comparison has been continuously hampered by the variability of computer performance. In traditional performance comparisons, the impact of performance variability is usually ignored (i.e., the means of performance measurements are compared regardless of the variability), or in the few cases where it is factored in using parametric confidence techniques, the confidence is either erroneously computed based on the distribution of performance measurements (with the implicit assumption that it obeys the normal law), instead of the distribution of sample mean of performance measurements, or too few measurements are considered for the distribution of sample mean to be normal. We first illustrate how such erroneous practices can lead to incorrect comparisons. Then, we propose a non-parametric Hierarchical Performance Testing (HPT) framework for performance comparison, which is significantly more practical than standard parametric techniques because it does not require to collect a large number of measurements in order to achieve a normal distribution of the sample mean. This HPT framework has been implemented as an open-source software.

Verifying the execution of a parallel program against a given memory consistency model (memory consistency verification) is a crucial problem in the functional validation of Chip Multiprocessor (CMP). In the absence of additional information, the above problem is known to be NP-hard. By adopting the pending period information, this paper proposes the first linear-time software-based approach to memory consistency verification. Our approach relies on a novel technique called reusable cycle checking, which reuses the previous order information when repeatedly checking cycle at different frontiers. In the context of pending period information, this technique significantly reduces the overall computational costs required by cycle checking, enabling linear-time (in the number of memory operations) memory consistency verification for any given multicore system with a constant number of processors. From a practical perspective, an industrial memory consistency verification tool, named XCHECK, has been developed based on our approach. XCHECK is capable of working with neither test program constraint nor dedicated hardware support in postsilicon verifications of many multiprocessor systems. Experimental results show that XCHECK is 3-10 times faster than a state-of-art software-based approach. XCHECK has been integrated into the verification platforms for an industrial multicore processor Godson-3B, and found several bugs of the design.

A widely adopted methodology for verifying the memory subsystem of a Chip Multiprocessor (CMP) is to verify executions of parallel test programs on the CMP against the given memory consistency model, which has been long known to be time consuming in both theory and practice. To accelerate memory consistency verification, previous approaches have to bear the cost of availability (e.g., relying on dedicated hardware supports that have not been offered by many commodity CMPs) or completeness (e.g., missing some bugs). In the meantime, the impact of parallel programs on memory consistency verification has more or less been overlooked. One piece of evidence is that few investigations have been dedicated to finding appropriate test programs enabling more efficient verification From a novel perspective of test program, we devise a practical technique called “program regularization,” which can effectively reduce the computation time of memory consistency verification. The key intuition behind program regularization is that any parallel program, if being reformed appropriately, can enable efficient memory consistency verification. More specifically, for an original program, program regularization introduces some auxiliary memory addresses, and periodically inserts load/store operations accessing these addresses to the original program. With the regularized program, memory consistency verification can be accomplished in linear time (with respect to the number of memory operations) when the number of processors is fixed. Experimental results show that program regularization can significantly accelerate memory consistency verification. Last but not least, our technique, which does not rely on concrete verification algorithm or dedicated hardware support, can be smoothly integrated into existing presilicon/postsilicon verification platforms of industrial CMPs to speed up memory consistency verification.

Coverage model is the main technique to evaluate the thoroughness of dynamic verification of a Design-under-Verification (DUV). However, rather than achieving a high coverage, the essential purpose of verification is to expose as many bugs as possible. In this paper, we propose a novel verification methodology that leverages the early bug prediction of a DUV to guide and assess related verification process. To be specific, this methodology utilizes predictive models built upon artificial neural networks (ANNs), which is capable of modeling the relationship between the high-level attributes of a design and its associated bug information. To evaluate the performance of constructed predictive model, we conduct experiments on some open source projects. Moreover, we demonstrate the usability and effectiveness of our proposed methodology via elaborating experiences from our industrial practices. Finally, discussions on the application of our methodology are presented.

Verifying memory consistency, which is to verify the executions of parallel test programs on a multiprocessor system against the given memory consistency model, is NP-hard. To accelerate verifying memory consistency in practice, we devise a technique called "program regularization". The key intuition behind program regularization is that a parallel program with some specific patterns can enable efficient verification. More specifically, for any original program, program regularization introduces some auxiliary memory locations, and periodically inserts store/load operations accessing these locations to the original program. With the regularized program, verifying memory consistency only requires a linear time complexity (with respect to the number of memory operations).

As a primary method for functional verification of microprocessors, simulation-based verification has received extensive studies over the last decade. Most investigations have been dedicated to the generation of stimuli (test cases), while relatively few has focused on explicitly reducing the redundant stimuli among the generated ones. In this paper, we propose an on-the-fly approach for reducing the stimuli redundancy based on machine learning techniques, which can learn from new knowledge in every cycle of simulation-based verification. Our approach can be easily embedded in traditional framework of simulation-based functional verification, and the experiments on an industrial microprocessor have validated that the approach is effective and efficient.

This paper describes a multi-FPGA based platform for emulating the Loongson-2G micro-processor on different mother boards. This platform is developed targeting at verification and evaluation of the Loongson-2G micro-processor, which is the next generation of Loongson-2 family, composed by one four-issue, out-of-order execution way 64-bit MIPS-compatible processor core named GS464, one 1M byte secondary Cache, one HyperTransport IO interface, one DDR2/3 memory interface and some other low speed IO interfaces. Most parts of this micro-process are mapped into the multi-FPGA based platform which consists two Vertex-5 330 FPGA chips. Semi-custom partitioning tactics within the entire design flow are developed to synthesize the whole designed into the multi-FPGA based platform. Modifications in architectural level are applied to the original architecture of the chip, in order to make it easy to be partitioned into two parts. High speed SEDES of HyperTransport IO link and DDR2/3 memory interface are emulated by using several clocks with different clock phases. To resolve the problem that hard to debug in FPGA system, a method by software probe with help of injected hardware modules in FPGA is developed and used to debug the problem causing by behavior mismatching between the ASIC ram block and the FPGA ram block. Some evaluation work on performance of Loongson-2G is done on this multi-FPGA based platform as pre-silicon test. To the authors' knowledge, there has been no previous work on such a big design used for verification and evaluation.

As technology advances both in increasing bandwidth and in reducing latency for I/O buses and devices, moving I/O data in/out memory has become critical. In this paper, we have observed the different characteristics of I/O and CPU memory reference behavior, and found the potential benefits of separating I/O data from CPU data. We propose a DMA cache technique to store I/O data in dedicated on-chip storage and present two DMA cache designs. The first design, Decoupled DMA Cache (DDC), adopts additional on-chip storage as the DMA cache to buffer I/O data. The second design, Partition-Based DMA Cache (PBDC), does not require additional on-chip storage, but can dynamically use some ways of the processor's last level cache (LLC) as the DMA cache. We have implemented and evaluated the two DMA cache designs by using an FPGA-based emulation platform and the memory reference traces of real-world applications. Experimental results show that, compared with the existing snooping-cache scheme, DDC can reduce memory access latency (in bus cycles) by 34.8% on average (up to 58.4%), while PBDC can achieve about 80% of DDC's performance improvements despite no additional on-chip storage.

Debugging parallel program is a well-known difficult problem. A promising method to facilitate debugging parallel program is using hardware support to achieve deterministic replay. A hardware-assisted deterministic replay scheme should have a small log size, as well as low design cost, to be feasible for adopting by industrial processors. To achieve the goals, we propose a novel and succinct hardware-assisted deterministic replay scheme named LReplay. The key innovation of LReplay is that instead of recording the logical time orders between instructions or instruction blocks as previous investigations, LReplay is built upon recording the pending period information [6]. According to the experimental results on Godson-3, the overall log size of LReplay is about 0.55B/K-Inst (byte per k-instruction) for sequential consistency, and 0.85B/K-Inst for Godson-3 consistency. The log size is smaller in an order of magnitude than state-of-art deterministic replay schemes incuring no performance loss. Furthermore, LReplay only consumes about $1.3%$ area of Godson-3, since it requires only trivial modifications to the existing components of Godson-3. The above features of LReplay demonstrate the potential of integrating hardware-assisted deterministic replay into future industrial processors.

This paper describes the scan test challenges and techniques used in the Godson-3 microprocessor, which is a scalable multicore processor based on the SMOC (scalable mesh of crossbar) on-chip network and targets high-end applications. Advanced techniques are adopted to achieve the scalable, low-power and low-cost scan architecture at the challenge of limited I/O resources and large scale of transistors. To achieve a scalable and flexible test access, a highly elaborate TAM (test access mechanism) is implemented with supporting multiple test instructions and test modes. Taking advantage of multiple cores embedding in the processor, scan partitions are employed to reduce test power and test time, and test compression with more than 10X compression ratio are utilized to decrease the scan chain length. To further decrease test time, a data-synchronous-comparator (DSC) is proposed for comparing the scan responses of the identical cores.

The verification of an execution against memory consistency is known to be NP-hard. This paper proposes a novel fast memory consistency verification method by identifying a new natural partial order: time order. In multiprocessor systems with store atomicity, a time order restriction exists between two operations whose pending periods are disjoint: the former operation in time order must be observed by the latter operation. Based on the time order restriction, memory consistency verification is localized: for any operation, both inferring related orders and checking related cycles need to take into account only a bounded number of operations. Our method has been implemented in a memory consistency verification tool for CMP (chip multi processor), named LCHECK. The time complexity of the algorithm in LCHECK is O(Cpp2n2) (where C is a constant, p is the number of processors and n is the number of operations) for soundly and completely checking, and O(p3n) for soundly but incompletely checking. LCHECK has been integrated into both pre and post silicon verification platforms of the Godson-3 microprocessor, and many bugs of memory consistency and cache coherence were found with the help of LCHECK.

Binary translation is one of the most important approaches for system migration. However, software binary translation systems often suffer from the inefficiency and traditional hardware-software co-designed virtual machines require the unavoidable re-design of the processor architecture. This paper presents a novel hardware-software co-designed method to accelerate the binary translation on an existing architecture. The hardware supports for source-architecture-only functions, partial decodes and binary translation system acceleration are proposed. These hardware supports help the binary translation system to achieve high performance and simplify the design of the binary translation software. In the meantime, the hardware cost is well controlled in a certain low level. These supports are implemented in Godson-3 processors to speedup the x86 binary translation to the native MIPS instruction set. Performance evaluations on RTL simulation and FPGA emulation platforms show that the proposed method can speedup most benchmark programs by nearly 10 times compared to pure software-based binary translation and achieves about 70% performance of the native program execution. The chip is fabricated in ST 65nm CMOS technology, and the physical design results show that the chip area cost is less than 5%.

A DSP method based on sub-sampling followed by M-point FFT of the sub-sampled signal is used to reduce the phase-locked loop's reference spur. To validate the system's effectiveness a digital calibration loop in SIMULINK is designed. The results show that the reference spur can be improved by 22 dBc with a 1% residual current mismatch and a 1 nA net value of leakage current.

The continuing shrinking of technology enables more and more processor cores to reside on a single chip. However, the power consumption and delay of global wires have presented a great challenge in designing future chip multiprocessors. With these overheads of wires properly accounted for, researchers have explored some efficient on- chip network designs in the domain of larger scale caches. While in the paper, we attempt to reduce the interconnect power consumption with a novel cache coherence protocol. Conventional coherence protocols are kept independent from underlying networks for flexibility reasons. But in CMPs, processor cores and the on-chip network are tightly integrated. Exposing features of interconnect networks to protocols will unveil some optimization opportunities for power reduction. Specifically, by utilizing the location information of cores on a chip, the coherence protocol we propose in this work chooses to response the requester with the data copy in the closest sharer of the desired cache line, other than fetching it from distant L2 cache banks. This mechanism reduces the hops cache lines must travel and eliminates the power that would have incurred on the corresponding not-traveled links. To get accurate and detailed power information of interconnects, we extract wire power parameters by physical level simulation (HSPICE) and obtain router power by synthesizing RTL with actual ASIC libraries. We conduct experiments on a 16-core CMP simulator with a group of SPLASH2 benchmarks. The results demonstrate that an average of 16.3% L2 cache accesses could be optimized, resulting in an average 9.3% power reduction of data links with 19.2% as the most. This mechanism also yields a performance speedup of 1.4%.

Dynamic voltage/frequency scaling (DVFS) has been widely applied to reduce the power dissipation of multi-cores processor. However, when applying DVFS, signals need to be synchronized between asynchronous clock domains with overhead of several cycles, which will result in performance penalty, and during frequency scaling the circuit cannot work. This paper proposes a novel variable frequency clock scheme in chip multiprocessors. In our scheme, processor cores running at different frequency can communicate with each other without the overhead of synchronizing signals. The results of simulation show that our scheme can achieve EDP improvement by 16.8%, with only 3.6% performance degradation.

With the development of semiconductor technology, microprocessors become more and more susceptible to transient faults. Some proposed schemes support redundant execution of a program in a superscalar processor for fault tolerance. However, they require a huge queue to accommodate interim states, which enlarge the hardware cost significantly. This paper analyzes the effect of halving a processor¿s instruction fetch bandwidth on a program¿s performance. We find that the performance degradation resulted from halving instruction fetch bandwidth declines when instruction latency is lengthened, branch prediction accuracy deteriorates or cache miss rate increases. Since an embedded microprocessor is characterized by long instruction latency, high branch misprediction rate and cache miss rate, a fault-tolerant scheme is proposed, in which two threads fetch instructions in turn and execute in the same processor core simultaneously without any extra queue. The simulation results from eight embedded applications show that performance penalty of our solution ranges from 6.5% to 30.1%, with an average of 22.5%, which is lower than that of the other proposed schemes. The experiment also indicates that our scheme can effectively detect faults occurring in the entire pipeline with short fault detection latency and minimal hardware cost. It is well suited for our solution to realize a reliable embedded microprocessor.

Conventional temporal redundant techniques to detect transient faults have resulted in considerable performance loss. One major reason for this problem is the reclamation of some critical resources, such as the instruction window and physical registers, is delayed, which degrades instruction-level parallelism. This paper proposes a novel fault-tolerant micro-architecture based on checkpoint mechanism. All occupied resources are reclaimed during the retirement stage in the first execution. Therefore, the performance overhead is mitigated evidently. Our scheme requires only small hardware cost and provides short fault detection latency.

As the gap between processing capability and bandwidth requirement of microprocessor increases, optical interconnects are used more and more widely in chip-to-chip data links. Trade-offs are made among latency, area, power consumption and reliability in the high frequency interconnect system in which error control schemes are always implemented to make it tolerate PER (packet error rate). In this paper, a scalable system for chip-to-chip optical interconnects is proposed and different types of error control schemes are compared using 90nm CMOS process. The goals are set to low latency, small area and low power consumption as well as acceptable MTTF (mean time to failure) for USR (ultra-short-reach) with very low BER (bit error rate). After that the ECS-HC based system is picked out and validated based on FPGA and 4.25Gbps 850nm optical transceivers.

This paper introduces the microarchitecture and logical implementation of SMT (Simultaneous Multithreading) improvement of Godson-2 processor which is a 64-bit, four-issue, out-of-order execution high performance processor. The condition for implementing correct memory consistency model in Godson-2 SMT processor is studied and a new register-level sharing and synchronization scheme is proposed. Godson-2 SMT processor has been implemented at the RTL level and simulated with the VstationPro of Mentor Graphics. The Linux operating system is ported to run in Godson-2 SMT processor and application programs such as SPEC CPU2000 benchmark suite are used to evaluate performance. Experimental results indicate that the performance of Godson-2 SMT processor is improved significantly by fully exploiting thread-level parallelism and optimized utilization of functional units. The average speedup is 31.3% with 18.8% area overhead.

The communication overhead has become one of the bottlenecks of SVM (shared virtual memory). Many methods have been taken to improve the performance of SVM. However, these can't obtain the improvement as expected. In order to get further utility of communication hardware and reduce unnecessary overhead, a prototype with the ability of RDMA is designed and implemented in This work, which is named FRAMP (virtual memory based Fast Remote direct memory Access and Message Passing network). FRAMP includes the cross bar-based switch, the custom host network interface and the user-level communication protocol. All of these are tightly coupled and deliberately balanced. FRAMP achieves 3.7 s one-way latency and 6.0 s RDMA read latency on system driver level. FRAMP gets 5.6 s one-way latency and 2.0 s ping-ping latency and 125MB/S asymptotic bandwidth on user API level with multi-thread programming method. Remote memory read for 8 bytes and a page of 4096 bytes only takes 8.0 s and 39 s respectively on user level. The obtained bandwidth is close to the hardware limit of our experimental environment, which is based on 33MHz 32-bit PCI bus, and the use rate of PCI bus is 94%. The SVM performance on FRAMP network with pure message passing is very good, but the one using RDMA read to fetch fault pages is not so good.

Most software DSMs use the interrupt mechanism for asynchronous message arrival notification. Interrupt, however, is expensive and may not be available in user-level communication protocols. This paper studies the performance of software DSMs using threads instead of interrupt for communication. We implement three thread communication methods in the JIAJIA software DSM. The first method separates a communication thread from the main thread, the second one divides the communication thread into a sending thread and a receiving thread, and the third method further splits a serving thread from the receiving thread. The effect of the thread communication methods is evaluated in a PC cluster and a cluster of PowerPC workstations with some well-accepted benchmarks. Evaluation results show that the performance of thread communication is slightly worse than that of interrupt communication when there is only one processor to run a process, but is better than that of interrupt communication when there are more than one processors in a node to run a process. The thread communication method with one sending thread and one receiving thread achieves the best performance inthethree thread communication methods. Besides, the effect of the thread communication is also related to the operating system. Analysis of the evaluation results reveals that the waiting time constitutes the major overhead of the execution, and the dominant factor that in uence waiting time is neither the interrupt overhead nor the thread switching overhead but the responsiveness of requests (i.e., whether requests can be processed and replied promptly).

A major overhead of software DSM is the long remote access latency when the accessed page is not in the focal cache. One method for tolerating the remote access latency is to prefetch the pages before they are accessed. This paper compares two methods of dynamic data prefetching-history prefetching, which utilizes the temporal locality of the program to prefetch, and aggregate prefetching, which utilizes the spatial locality of the program to prefetch-on the JIAJIA software DSM. Experiments with eight well-accepted benchmarks and a real application show that both can dramatically reduce the number of remote page faults and the number of messages exchanged. All applications benefit from the prefetching in overall running time, and four achieve a performance improvement of 10%-20%. We then analyze the advantages and disadvantages of the two prefetching strategies. We find that aggregate prefetching may be more efficient than history prefetching for most applications in software DSM systems.

Write detection is essential in multiple-writer protocols to identify writes to shared pages so that these writes can be correctly propagated. Software DSMs that implement multiple-writer protocol normally employ the virtual memory page fault to detect writes to shared pages. It write-protects shared pages at the beginning of an interval to detect writes of the interval. This paper proposes a new write detection scheme in a home-based software DSM called JIAJIA. It automatically recognizes single write to a shared page by its home host and assumes the page will continue to be written by the home host in the future until the page is written by remote hosts. During the period the page is assumed to be singly written by its home host, no write detection of this home page is required and page faults caused by home host write detection call are avoided. Evaluation with some well-known DSM benchmarks reveals that the new write detection can reduce page faults dramatically and improve performance significantly.

Dynamic task migration is an effective strategy to maximize the performance and resource utilization in metacomputing environments. Traditionally, however, a "task" means only the corresponding code of computation, i.e., the data related to this computation is usually neglected. As such, when one task is migrated from processor A to processor B, the data required by this task remains on processor A. Thus, the processor B has to perform remote communication when it executes this task, eliminating the advantage of task migration, or even further degrading the performance. Hence, the definition of the traditional "task" should be revisited. We define a task as follows: Task=Computation subtask+Data subtask. Computation subtask is the program code to be executed, while the data subtask is the operations to access the related data located in memory. In fact, as the speed gap between processors and memory becomes larger and larger, the importance of data subtask becomes more obvious than before. Therefore, we argue that both subtasks should be migrated to a new processor during task migration. Based on this observation, we propose a dynamic loop-level task migration scheme. This scheme is implemented within the context of the JIAJIA software DSM system (W. Ha et al., 1999). The evaluation results show that the task migration scheme improves the performance of our benchmark applications by 36% to 50% compared with static task allocation schemes. As a result, the new scheme performs an average of 30% better than other computation-only migration schemes.

The complexity of a multiprocessor memory system grows with the endeavors people make to improve the performance. The pseudo and real execution graphs introduced here can formally describe the complex event ordering behavior of the multiprocessor memory system and to verify the correctness of a parallel program under a consistency model. A pseudo execution graph represents the programmer's abstraction of an execution in which memory accesses are simple, atomic operations. A loop in the pseudo execution graph indicates an incorrect execution. A real execution graph represents the hardware designer's abstraction of an execution in which each memory access is a causal sequence of events. A loop in the real execution graph indicates that this execution is impossible to occur. A program is correct if all loops in the pseudo execution graphs cause loops in the corresponding real execution graphs.