We present efficient all-to-all personalized communication algorithms for a 2D torus in wormhole-routed networks. Our complete exchange algorithms reduce the number of start-up by a factor of up to 2, which is a good metric for network performance in wormhole networks. Our algorithms divide the whole network into 22 networks, giving two contention-free networks with N/2N/2. After specially designated nodes called master nodes have collected messages, whose destinations are the rest of the basic cells, only master nodes perform complete exchange with a reduced network size. When finished with this complete exchange among master nodes, these nodes distribute messages to the rest of the master nodes, which results in the desired complete exchange. Then, we present a modified algorithm that further reduces the data transmission time sacrificing the start-up time. After we present our new algorithms, we analyze time complexities and compare several algorithms. We show that our practical algorithm is efficient by a factor of 2 in the required start-up time which means that our algorithms are suitable for wormhole-routed networks.

We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.

Motion estimation is a major part of the video coding, which traces the motion of moving objects in video sequences. Among various motion estimation algorithms, the Hierarchical Block-Matching Algorithm (HBMA) that is a multilayered motion estimation algorithm is attractive in motion-compensated interpolation when accurate motion estimation is required. However, parallel processing of HBMA is necessary since the high computational complexity of HBMA prevents it from operating in real-time. Further, the repeated updates of vectors naturally lead to pipelined processing. In this paper, we present a pipelined architecture for HBMA. We investigate the data dependency of HBMA and the requirements of the pipeline to operate synchronously. Each pipeline stage of the proposed architecture consists of a systolic array for the block-matching algorithm, a bilinear interpolator, and a latch mechanism. The latch mechanism mainly resolves the data dependency and arranges the data flow in a synchronous way. The proposed architecture achieves nearly linear speedup without additional hardware cost over a non-pipelined one. It requires the clock of 2.70 ns to process a large size of frame (e.q. HDTV) in real-time, which is about to be available under the current VLSI technology.

Advances in ILP techniques enable strict consistency models to relax memory order through speculative execution of memory operations. However, ordering constraints still hinder the performance because speculatively executed operations cannot be committed out of program order for the possibility of mis-speculation. In this paper, we propose a new technique which allows memory operations to be non-speculatively committed out of order without violating consistency constraints. Consistency constraints are guaranteed through delaying the coherence requests. The proposed technique also improves the performance of spin lock primitives such as TTS lock or MCS lock. Through delaying early acquire requests, the lock transfer time can be improved when there is high contention for a lock.

The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimeze both timeliness and reliability. The performance measure in responsive systems is responsiveness that tells how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocols and specification, we believe that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss the scheduling problem in responsive systems. At first, we investigate the issues in the scheduling and propose the precise definition of the responsiveness. We also suggest a scheduling algorithm called Responsive Earliest Deadline First (REDF) for preemptive aperiodic tasks in a uniprocessor system. We show that REDF is optimal to obtain the maximum responsiveness, and the time complexity is analyzed to be (N 2N). By illustrating a contradictory example, it is shown that REDF can be enhanced if a constraint on tasks is released.

To reduce the memory access latency on sharedmemory multiprocessors, several prefetching schemes have been proposed. The sequential prefetching scheme is a simple hardware-controlled scheme, which exploits the sequentiality of memory accesses to predict which blocks will be read in the near future. Aggressive sequential prefetching prefetches many blocks on each miss to reduce the miss rates and results in good performance for application programs with high sequentiality. However, conservative sequential prefetching prefetches a few blocks on each miss to avoid prefetching of useless blocks, which shows better performance than aggressive sequential prefetching for application programs with low sequentiality. We analyze the relationship between the sequentiality of application programs and the effectiveness of sequential prefetching on various memory and network latency and propose a new adaptive sequential prefetching scheme. Simply adding a small table to the sequential prefetching scheme, the proposed scheme prefetches a large number of blocks for application programs with high sequentiality and reduces the miss rates significantly, and prefetches a small number of blocks for application programs with low sequentiality and avoids loading useless blocks.

In this paper, we propose a call arrival history-based location tracking strategy for a variable call arrival rate over time. The basis of the proposed strategy is a time-based location tracking strategy. A mobile terminal obtains the up-to-date information about changes in the call arrival rate by maintaining its call arrival history, from which it can calculate an appropriate timeout interval for a variable call arrival rate. We present a simple analytical model and numerical results to investigate its performance for both a fixed and a variable call arrival rate which is modeled by a Markov-modulated Poisson process.