Browsing by Author "Shann, JJJ"

Now showing 1 - 13 of 13

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.
Aggressive scheduling for memory accesses of CISC superscalar microprocessors
(2001-09-01)
Shiu, RM
;
Hwang, HY
;
Shann, JJJ
;
資訊工程學系
;
Department of Computer Science
For CISC microprocessors, the proportion of memory access instructions is relatively high, and a specific address is likely to be accessed repeatedly in a short period of time because of register-to-memory or memory-to-memory instruction set architectures and limited register sets. As superscalar architectures advance, an aggressive scheduling policy for memory access becomes crucial. In this paper, we examine the scheduling policies of loads/stores on CISC superscalar processors and develop an aggressive scheduling policy called preload. The preload scheduling policy allows loads to precede the earlier unsolved pending stores, and delays the checking of conflict and forwarding of data until the data is loaded, thereby allowing greater tolerance of the latency for address generation. Because of its popularity, we focus our attention on the x86 instruction set. Simulation results show that the preload achieves a higher performance in comparison with the traditional scheduling policies such as load bypassing and load forwarding. Furthermore, by reducing the pipeline stages, the preload can achieve even higher performance.
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.
An X86 load/store unit with aggressive scheduling of load/store operations
(1998)
Hwang, HY
;
Shiu, RM
;
Shann, JJJ
;
資訊工程學系
;
Department of Computer Science
Because of register-memory instruction set architecture and limited register set, there are significant amounts of memory access instructions in x86 microprocessors. As the higher issue degree of superscalar microprocessor is provided, an aggressive scheduling policy of load/store operations becomes crucial. In this paper, we examine the scheduling policies of loads/stores on x86 superscalar microprocessors and propose a new aggressive scheduling policy called load speculation, which allows loads to precede the previous unsolved pending stores. Simulation results show that the load speculation achieves the higher performance in comparison with the traditional scheduling policies such as load bypassing and load forwarding. Furthermore, by reducing the pipeline stages, the load speculation can achieve even higher performance.
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.
Decoding of CISC instructions in superscalar processors with high issue rate
(2000-03-01)
Shiu, RM
;
Chiu, JC
;
Cheng, SK
;
Shann, JJJ
;
資訊工程學系
The paper examines the design issues of decoders, including the primitive operation (POP) translation strategies and the decoding rules, for CISC superscalar processors to exploit a higher degree of parallel execution. Attention is focused on the x 86 instruction set because of its popularity. There are two different approaches regarding POP translation strategies: one is to merge the address generation into load/store operations, and the other is to translate the isolated address generation operations. Simulation results show that, in high issue-rate decoders, the latter strategy improves the performance by 20 to 25 %. Furthermore, considering the tradeoffs between the hardware cost and performance, a cost-effective decoding rule suitable for current commercial programs is recommended.
Decoding unit with high issue rate for X86 superscalar microprocessors
(1998)
Cheng, SK
;
Shiu, RM
;
Shann, JJJ
;
資訊工程學系
;
Department of Computer Science
In the new generation of x86 microprocessors, superscalar techniques are used to achieve higher performance by executing multiple instructions in parallel. For compatibility and higher execution parallelism, the decoding units of these microprocessors translate the x86 instructions into primitive operations. These microprocessors translate x86 instructions by the similar rca? of merging address generating into load/store operations. In this paper, we develop a nerv translating strategy of translating isolated address generation operations. Simulation results show that, in high issue rate decoding units, translating isolated address generation operations improves the performance for 20% to 25%. Besides, we find that enhancing the store buffer with the ability of snooping result buses is important for high issue rate decoding units. Furthermore, considering the tradeoff of the hardware cast and performance, we examine the decoding rules to design a decoding unit. According to the simulation results,,ve suggest a good decoding rule suitable for current commercial programs.
Fast query evaluation through document identifier assignment for inverted file-based information retrieval systems
(2006-05-01)
Cheng, CS
;
Chung, CP
;
Shann, JJJ
;
資訊工程學系
;
Department of Computer Science
Compressing an inverted file can greatly improve query performance of an information retrieval system (IRS) by reducing disk I/Os. We observe that a good document identifier assignment (DIA) can make the document identifiers in the posting lists more clustered, and result in better compression as well as shorter query processing time. In this paper, we tackle the NP-complete problem of finding an optimal DIA to minimize the average query processing time in an IRS when the probability distribution of query terms is given. We indicate that the greedy nearest neighbor (Greedy-NN) algorithm can provide excellent performance for this problem. However, the Greedy-NN algorithm is inappropriate if used in large-scale IRSs, due to its high complexity O(N-2 x n), where N denotes the number of documents and n denotes the number of distinct terms. In real-world IRSs, the distribution of query terms is skewed. Based on this fact, we propose a fast O(N x n) heuristic, called partition-based document identifier assignment (PBDIA) algorithm, which can efficiently assign consecutive document identifiers to those documents containing frequently used query terms, and improve compression efficiency of the posting lists for those terms. This can result in reduced query processing time. The experimental results show that the PBDIA algorithm can yield a competitive performance versus the Greedy-NN for the DIA problem, and that this optimization problem has significant advantages for both long queries and parallel information retrieval (IR). (c) 2005 Elsevier Ltd. All rights reserved.
Inverted file compression through document identifier reassignment
(2003-01-01)
Shieh, WY
;
Chen, TF
;
Shann, JJJ
;
Chung, CP
;
資訊工程學系
The inverted file is the most popular indexing mechanism for document search in an information retrieval system. Compressing an inverted file can greatly improve document search rate. Traditionally, the d-gap technique is used in the inverted file compression by replacing document identifiers with usually much smaller gap values. However, fluctuating gap values cannot be efficiently compressed by some well-known prefix-free codes. To smoothen and reduce the gap values, we propose a document-identifier reassignment algorithm. This reassignment is based on a similarity factor between documents. We generate a reassignment order for all documents according to the similarity to reassign closer identifiers to the documents having closer relationships. Simulation results show that the average gap values of sample inverted files can be reduced by 30%, and the compression rate of d-gapped inverted file with prefix-free codes can be improved by 15%. (C) 2002 Elsevier Science Ltd. All rights reserved.
Low-power BIBITS encoding with register relabeling for instruction bus
(2005)
Cheng, CT
;
Chiao, WH
;
Shann, JJJ
;
Chung, CP
;
Chen, WF
Reducing power consumption of embedded system has gained much attention recently. Reducing memory bus switchings is an effective way to reduce system power since memory bus power constitutes a great portion of the system power. While many techniques exist for reducing bus power in address buses, only a few have been proposed for content-bus power reduction. We propose a Bus-Invert and Bus-Invert with transition signaling (BIBITS) encoding scheme to reduce power consumption on instruction bus. An instruction is partitioned into fields according to its format. Four elementary Boolean functions are used as encoding functions. BIBITS uses the most suitable encoding functions for different instruction partitions. We also propose a register relabeling algorithm for BIBITS encoding to further reduce bit switchings on register fields. Simulation results show that the overall average switching reduction is 64% of unencoded bus, 59% of the previous register relabeling scheme, and 33% of Petrov's bus encoding scheme. Compared with Petrov's bus encoding scheme, our scheme uses a decoding signal table only half the size to encode all basic blocks.
Low-power branch prediction
(2005)
Hu, YC
;
Chiao, WH
;
Shann, JJJ
;
Chung, CP
;
Chen, WF
Low-power design has gained much attention recently, especially for computing on battery-powered equipments. Reducing BTB (branch target buffer) accesses is an effective way to reduce processor power consumption, since BTB consumes a significant portion of power in a processor. In this paper, we propose two approaches to reduce BTB accesses. The first approach expects the distance of every two dynamic branch instructions to be a constant n, where n can be statically profiled, and forces BTB to repose for n instructions after a BTB hit. The second approach dynamically predicts the address of the next branch instruction, and accesses BTB only on the predicted address. Multimedia/DSP benchmarks are used in our evaluation. Experimental results show that these methods can potentially reduce 22-033% of all BTB accesses.
Low-power data address bus encoding method
(2005)
Weng, TH
;
Chiao, WH
;
Shann, JJJ
;
Chung, CP
;
Lu, J
Reducing power consumption of computer systems has gained much research attention recently In a typical system, the memory bus power constitute will over 50% of all system power; and this power is required due to bus signal transitions (0 41 or 140). Reducing the number of memory bus transitions is hence an effective way to reduce system power While many techniques deal with reducing bus power on instruction address bus, only a few have been proposed for data address bus power reduction. We present an encoding scheme to reduce data address bus power consumption. In this scheme, data address bus can be frozen for sequential addresses, or inverted as appropriate for other cases. Furthermore, data addresses are classified info read addresses and write addresses, and each address set is encoded independently. Simulation results show that the overall bus line switching reduction is 26% of unencoded bus, or 14.5% of the previous T0_BI method [1].
Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems
(2006-03-01)
Cheng, CS
;
Shann, JJJ
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
This paper presents a size reduction method for the inverted file, the most suitable indexing structure for an information retrieval system (IRS). We notice that in an inverted file the document identifiers for a given word are usually clustered. While this Clustering property can be used in reducing the size of the inverted file, good compression as well as fast decompression must both be available. In this paper, we present it method that can facilitate coding and decoding processes for interpolative coding using recursion elimination and loop unwinding. We call this method the unique-order interpolative coding. It can calculate the lower and upper bounds of every document identifier for a binary code without using a recursive process, hence the decompression time can be greatly reduced. Moreover, it also can exploit document identifier Clustering to compress the inverted file efficiently. Compared with the other well-known compression methods, our method provides fast decoding speed and excellent compression. This method can also be used to support a self-indexing strategy. Therefore our research work in this paper provides a feasible way to build a fast and space-economical IRS. (c) 2005 Elsevier Ltd. All rights reserved.