Browsing by Author "Chung, CP"

Now showing 1 - 20 of 43

3-disjoint gamma interconnection networks
(2003-05-15)
Chen, CW
;
Lu, NP
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a new multistage interconnection network, called 3-disjoint gamma interconnection network (3DGIN). The 3DGIN is a modified gamma interconnection network that provides 3-disjoint paths to tolerate two switch or link faults between any source and destination pairs. The 3DGIN has lower hardware cost than GIN; furthermore, the routing and rerouting tags to generate 3-disjoint paths can be obtained in O(logN) time. To show the advantage features of 3DGIN, we also make a comparison between the gamma-related networks, the GIN, enhanced IADM, and 3DGIN. (C) 2002 Elsevier Science Inc. All rights reserved.
A dominance relation enhanced branch-and-bound task allocation
(2001-09-01)
Ma, YC
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
We investigate the task allocation problem of allocating a parallel program on parallel processors with non-uniform communication latencies. A branch-and-bound algorithm with a dominance relation is proposed to obtain an optimal task assignment. The key observation on deriving the dominance relation is that tasks can be clustered according to communication weights. The dominance relation is effective to prune the search space when the task clustering boundary - a small cut - is met. The proposed algorithm is compared to the A*-algorithm for task allocation. Experiment shows that our proposed algorithm achieves a speed-up ranging from 1.02 to 1.68, depending on the degree of task clustering and parallelism. This shows the effectiveness of the proposed dominance relation. (C) 2001 Elsevier Science Inc. All rights reserved.
A fault-tolerant multistage combining network
(1996-04-10)
Lu, NP
;
Chung, CP
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
In this paper, we propose a solution to both fault tolerance and hot-spot contention problems in multiprocessor systems with multistage interconnection networks. Combining networks are known to be effective in handling hot-spot traffic. However, the fault tolerance capability of unique-path combining network is insufficient and must be enhanced. Thus, we use the chaining scheme, which provides alternate routing paths by connecting intrastage switching elements with a chain, to enhance the fault tolerance capability of combining network. As a result, we propose a chained combining network. Because of the bidirectionality of combining networks, we also develop routing procedures for the chained combining network. With slight modifications, these routing procedures can also be used in other multipath fault-tolerant combining networks. (C) 1996 Academic Press, Inc.
A software/hardware cooperated stack operations folding model for Java processors
(2004-08-01)
Ton, LR
;
Chang, LC
;
Shann, JJ
;
Chung, CP
;
資訊工程學系
Java has become the most important language in the Internet area, but the execution performance of Java processors is severely limited by the true data dependency inherited from the stack architecture defined by Sun's Java Virtual Machine. A sequential hardware-based folding algorithm-POC folding model was proposed in the earlier research to eliminate up to 80.1% of stack push and pop bytecodes. The remaining stack push and pop bytecodes cannot be folded due to the sequential checking characteristic of the POC folding model. In this paper, a new software/hardware cooperated folding algorithm-T-POC (Tagged-POC) folding model is proposed to enhance the folding ability of the POC-based Java processors to fold the remaining stack push and pop bytecodes. While executing the bytecodes, bytecode grouping and rescheduling are done by a T-POC bytecode rescheduler to generate the new binary class images in memory. With the cooperation of the hardware-based POC folding model, higher execution performance can be achieved by executing the newly generated class images. Statistical data show that 94.8% of stack push and pop bytecodes can be folded, and the overall execution speedups of 2-, 3-, and 4-foldable strategies are 1.72, 1.73 and 1.74, respectively, as compared to a single-pipelined stack machine without folding. (C) 2003 Elsevier Inc. All rights reserved.
A statistics-based approach to incrementally update inverted files
(2003)
Shieh, WY
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
Many information retrieval systems use the inverted file as indexing structure. The inverted file, however, is not suited to supporting incremental updates when new documents are to be added to an existing collection. Most studies suggest dealing with this problem by sparing free space in an inverted file for future updates. In this paper, we propose a run-time statistics-based approach to allocate the spare space. This approach estimates the space requirements in an inverted file using only a little most recent statistical data on space usage and document update request rate. For best indexing speed and space efficiency, the amount of the spare space to be allocated is determined by adaptively balancing the trade-offs between reorganization count and space utilization. Simulation results show that the proposed space-sparing approach significantly avoids reorganization in updating an inverted-file, and in the meantime, unused free space can be well controlled such that the file access speed is not affected.
A statistics-based approach to incrementally update inverted files
(2005-03-01)
Shieh, WY
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
Many information retrieval systems use the inverted file as indexing structure. The inverted file, however, requires inefficient reorganization when new documents are to be added to an existing collection. Most studies suggest dealing with this problem by sparing free space in an inverted file for incremental updates. In this paper, we propose a run-time statistics-based approach to allocate the spare space. This approach estimates the space requirements in an inverted file using only a little most recent statistical data on space usage and document update request rate. For best indexing speed and space efficiency, the amount of the spare space to be allocated is determined by adaptively balancing the trade-offs between reorganization reduction and space utilization. Experiment results show that the proposed space-sparing approach significantly avoids reorganization in updating an inverted file, and in the meantime, unused free space can be well controlled such that the file access speed is not affected. (C) 2003 Elsevier Ltd. All rights reserved.
A tree-based inverted file for fast ranked-document retrieval
(2003)
Shieh, WY
;
Chen, TF
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
Inverted files are widely used to index documents in large-scale information retrieval systems. An inverted file consists of posting lists, which can be stored in either a document-identifier ascending order or a document-weight descending order. For an identfier-ascending-order posting list, retrieving ranked documents necessitates traversal of all postings, whereas for the weight-descending-order posting list, performing Boolean queries involves very complex processing. In this paper, we transform a posting list to a tree-based structure, called the n-key-heap posting tree, to speedup ranked-document retrieval for Boolean queries. In this structure, the orders of document identfiers and document weights are preserved simultaneously. To preserve the identifier order, the edge pointers are designed to maintain numerical order in the posting tree. To preserve the weight order, greater-weight postings are stored in higher tree nodes by the heap property. We model these criteria to a tree-construction problem and propose an efficient algorithm to construct an optimal posting tree having the minimal access time.
A unique-order interpolative code for fast querying and space-efficient indexing in information retrieval systems
(2004)
Cheng, CS
;
Shann, JJJ
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
The word positions for any given word in the whole collection are arranged in clusters. If we can use the method that can take advantage of clustering, excellent results can be achieved in compression of inverted file. However, the mechanisms of decoding in all the well-known compression methods that can exploit clustering are more complex, which reduce the ability of searching performance in information retrieval system (IRS) at some degree. In this paper, we proposed a new method that can facilitate coding and decoding of interpolative code by using the simply applied and high-speed models such as gamma code and Golomb code in d-gap technique. This new method can exploit clustering well, and the experimental results confirm that our method can provide fast decoding speed and excellent compression efficiency.
An analytical POC stack operations folding for continuous and discontinuous Java bytecodes
(2002-09-01)
Ton, LR
;
Chang, LC
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
The execution performance of a stack-based Java virtual machine (JVM) is limited by the true data dependency. To enhance the performance of the JVM, a stack operations folding mechanism for the picoJava-I/II processor was proposed by Sun Microsystems to fold 42.3% stack operations. By comparing the continuous bytecodes with predefined folding patterns in instruction decoder, the number of push/pop operations in between the operand stack and the local variable could be reduced. In this study, an enhanced POC (EPOC) folding model is proposed to further fold the discontinuous bytecodes that cannot be folded in continuous bytecodes folding mechanisms. By proposing a stack re-order buffer (SROB) to help the folding check processes, the EPOC folding model can fold the stack operations perfectly with a small size of SROB implementation. Statistical data shows that the four-foldable strategy of the EPOC folding model can eliminate 98.8% of push/pop operations with an instruction buffer size of 7 bytes and the SROB size of eight entries. (C) 2002 Elsevier Science B.V. All rights reserved.
An approximate agreement algorithm for wraparound meshes
(1995-09-01)
Cheng, RL
;
Chung, CP
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
An appropriate algorithm, the neighboring exchange, for reaching an approximate agreement in a wraparound mesh is proposed. The algorithm is characterized by its isotropic nature, which is of particular usefulness when applied in any symmetric system. The behavior of this algorithm can be depicted by recurrence relations which can be used to derive the convergence rate. The convergence rate is meaningful when the algorithm is used to synchnize clocks. The rate of synchronizing clocks is derived, and it can be applied to all wraparound meshes with practical scale. With the recurrence relations, we also prove the correctness of this algorithm.
An inverted file cache for fast information retrieval
(2003-07-01)
Shieh, WY
;
Shann, JJJ
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
The inverted file is the most popular indexing mechanism used for document search in an information retrieval system (IRS). However, the disk I/O for accessing the inverted file becomes a bottleneck in an IRS. To avoid using the disk I/O, we propose a caching mechanism for accessing the inverted file, called the inverted file cache (IF cache). In this cache, a proposed hashing scheme using a linked list structure to handle collisions in the hash table speeds up entry indexing. Furthermore, the replacement and storage mechanisms of this cache are designed specifically for the inverted file structure. We experimentally verify our design, based on documents collected from the TREC (Text REtrieval Conference) and search requests generated by the Zipf-like distribution. Simulation results show that the IF cache can improve the performance of a test IRS by about 60% in terms of the average searching response time.
Applying stack simulation for branch target buffers
(2000-05-15)
Shiu, RM
;
Lu, NP
;
Chung, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Branch target buffer (BTB) is widely used in modern microprocessor designs to reduce the penalties caused by branches. To evaluate the performance of a BTB, trace-driven simulation is often used. However, as the trace of a typical program is very large, the simulation time is often too long. To reduce the simulation time, we developed a stack simulation technique for BTB to evaluate many sets of design parameters in one simulation pass. Due to the fact that the prediction information in the BTB does not have the inclusion property - a property which makes the stack simulation work, we propose a state vector method to enumerate the prediction information for different sets of BTB design parameters to mimic the inclusion property. Simulation results show that the state vector method greatly reduces the simulation time. The speedup of the stack simulation for BTB proposed in this paper over the traditional BTB simulation is 4.68 in terms of simulation time when 13 sets of BTB design parameters are simulated in one simulation pass. (C) 2000 Elsevier Science Inc. All rights reserved.
Branch-and-bound task allocation with task clustering-based pruning
(2004-11-01)
Ma, YC
;
Chen, TF
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state-space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state-space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state-space searching approach feasible for practical use. (C) 2004 Published by Elsevier Inc.
Code compression by register operand dependency
(2002)
Lin, K
;
Shann, JJJ
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
This paper proposes a dictionary-based code compression technique that maps the source register operands to the nearest occurrence of a destination register in the predecessor instructions. The key idea is that most destination registers have a great possibility to be used as source registers in the following instructions. The dependent registers can be removed from the dictionary if this information can be specified otherwise. As a result, the compression ratio benefits from the decreased dictionary size. A set of programs has been compressed using this feature. The compression results show that the average compression ratio is reduced to 38.6% on average for MediaBench benchmarks compiled for MIPS R2000 processor.
Code compression techniques using operand field remapping
(2002-01-01)
Lin, K
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
Dictionary-based code compression stores the most frequently used instruction sequences in a dictionary, and replaces the occurrences of these sequences in the program with codewords. The large dictionary size is due mainly to many instruction sequences which are different only in operands, but are otherwise the same. The operand factorisation technique divides the expression tree into tree-pattern (opcode sequence) and operand-pattern (operand sequence) to reduce this redundancy; instruction sequences with the same opcodes but different operands may thus share the same tree-pattern dictionary entry. The paper proposes an operand field remapping method to further reduce dictionary size. The key idea is to explore the relations between the current operand to be compressed with those already compressed. The operand-pattern dictionary is therefore divided into an operand remapping dictionary and an operand list dictionary. Each entry in the operand remapping dictionary indicates whether the operand (register or immediate value) to be compressed is the most used operand, the same as the destination register of the previous instructions, or otherwise. With this remapping technique, the operand dictionary size is greatly reduced. An average 46% compression ratio can be achieved where compression ratio = (dictionary size + compressed code size)/(original program size).
Delayed precise invalidation - A software cache coherence scheme
(1996-09-01)
Hwang, TS
;
Lu, NP
;
Chung, CP
;
交大名義發表
;
資訊工程學系
Software cache coherence schemes are very desirable in the design of scalable multiprocessors and massively parallel processors. The authors propose a software cache coherence scheme named 'delayed precise invalidation' (DPI). DPI is based on compiler-time markings of references and a hardware local invalidation of stale data in parallel and selectively. With a small amount of additional hardware and a small set of cache management instructions, this scheme provides more cacheability and allows invalidation of partial elements in an array, overcoming some inefficiencies and deficiencies of previous software cache coherence schemes.
Design of an optimal folding mechanism for Java processors
(2002-11-10)
Ton, LR
;
Chang, LC
;
Shann, JJ
;
Chung, CP
;
資訊工程學系
Java has become the most important language in the Internet area, but its execution performance is severely limited by the true data dependency inherited from the stack architecture defined by the Sun's Java Virtual Machine (JVM). To enhance the performance of the JVM, a stack operations folding mechanism for the picoJava-II processor was proposed by Sun Microsystems to fold 42.3% stack push/pop instructions. A systematic folding algorithm-Producer, Operator, and Consumer (POC) folding model was proposed in the earlier research to eliminate up to 82.9% of stack push/pop instructions. The remaining push and pop instructions cannot be folded due to the sequential checking characteristic of the POC folding model. A new folding algorithm-enhanced POC (EPOC) folding model is proposed in this paper to further fold the remaining push and pop instructions. In the EPOC folding model, stack push/pop instructions are folded with the proposed Stack Reorder Buffer (SROB) architecture. With a small SROB size of 584 bits, almost all of the stack push/pop instructions can be folded with the precise exception handling capability. Statistical data shows that 98.8% of the stack push/pop instructions can be folded, and the average execution performance speedup of a 4-foldable processor with a 7-byte instruction buffer is 1.74 as compared to a traditional single-pipelined stack machine without folding. (C) 2002 Elsevier Science B.V. All rights reserved.
Design of instruction address queue for high degree x86 superscalar architectures
(2002-05-01)
Chiu, JC
;
Wang, MJY
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
A major hurdle of recent x86 superscalar processor designs is limited instruction issue rate due to the overly complex x86 instruction formats. To alleviate this problem, the machine states must be preserved and the instruction address routing paths must be simplified. We propose an instruction address queue, whose queue size has been estimated to handle saving of instruction addresses with three operations: allocation, access, and retirement. The instruction address queue will supply the stored instruction addresses as data for three mechanisms: changing instruction flow, updating BTB, and handling exceptions. It can also be used for internal snooping to solve self-modified code problems. Two CISC hazards in the x86 architectures, the variable instruction length and the complex addressing mode, have been considered in this design. Instead of the simple full associative storing method in lower degree (< 4) superscalar systems, the line-offset method is used in this address queue. This will reduce by 1/3 the storage space for a degree-5 superscalar x86 processor with even smaller access latency. We use synthesis tools to analyze the design, and show that it produces optimized results. Because the address queue design can keep two different line addresses in an instruction access per cycle, this method can be extended for designing a multiple instruction block issue system, such as the trace processor.
Design of instruction stream buffer with trace support for x86 processors
(2000)
Chiu, JC
;
Huang, IH
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
The potential performance of superscalar microprocessors can be exploited only when fed with sufficient instruction bandwidth. The front-end units, the instruction stream buffer and the fetcher, are the key elements achieving this goal. In most current processors, instruction stream buffers cannot support the instruction sequence beyond a basic block. The fetch rates ale constrained by the branch barriers. In x86 processors, the split-line instruction problem worsens this constraint. We propose a design to improve instruction stream buffer performance by coupling it with BTB to support trace prediction. According to the simulation results of such an instruction stream buffer; the maximum fetch bandwidth can reach 8.42 x86 instructions per cycle. Furthermore, we suggest that the instruction stream buffer consist of two 64-bytes entries. Compared with other existing designs, this instruction stream buffer can improve performance by 90% over current x86 processor instruction fetching on average.
Designing a disjoint paths interconnection network with fault tolerance and collision solving
(2005-10-01)
Chen, CW
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
In fault-tolerant interconnection designs, many prior researches suggest good use of disjoint paths to improve the reliability of interconnection networks. Although disjoint paths increase reliability, they always cost the throughput penalty. To address the problems of both performance and fault-tolerant capability, the following issues should be carefully considered: (1) guarantee of at least two disjoint paths, (2) easy rerouting between disjoint paths, (3) keep low rerouting hops, (4) solve the occurrences of packets' collision. In this paper, we consider these issues to design a fault-tolerant network called CSMIN (Combining Switches Multistage Interconnection Network). CSMIN provides two disjoint paths to guarantee one fault-tolerant and can dynamically reroute packets between these two paths to solve the collision situation. In other words, to switch packets between these two disjoint paths easily, CSMIN causes these two disjoint paths to have regular distances at each stage. Accordingly, a packet can be dynamically sent to the other disjoint path if it encounters a faulty or busy element. In addition, CSMIN presents low rerouting hops (an average of one rerouting hop) to maintain a low collision ratio. From the simulation result, CSMIN performs with a better arrival ratio than Gamma and other related disjoint paths networks do.