In this paper, the forward link erlang capacity and outage probability for hierarchical cellular system based on 2 layer macrocell/microcell are derived analytically by considering the impact of imperfect power control and soft hand-off. The analysis on the outage probability is carried out using two methods: lognormal approximation and Chernoff upper bound. We assume that voice and multi-rate data service users are distributed uniformly in each cell and the same spectrum is applied in both layers. In addition, we take into account the base station transmission power ratio between tiers and the relative position of microcell having island distribution in macrocell. The forward link interference is evaluated by using Monte-Carlo simulation introduced in [2]. In this paper, we compare the forward link erlang capacity of 1x system to 3x system and show that 3x system can increase the user capacity by 3.4 times in case of macrocell and microcell, respectively, compared to 1x system.

This paper introduces the concept of hierarchical testability of data paths for delay faults. A definition of hierarchically two-pattern testable (HTPT) data path is developed. Also, a design for testability (DFT) method is presented to augment a data path to become an HTPT one. The DFT method incorporates a graph-based analysis of an HTPT data path and makes use of some graph algorithms. The proposed method can provide similar advantages to the enhanced scan approach at a much lower hardware overhead cost.

The understanding of instruction set usage in typical DOS/Windows applications plays a very important role in designing high performance x86 compatible microprocessors. This paper presents the tools to such analysis, the analysis results, and their implications on the design of a RISC-based superscalar processor for efficient x86 instruction execution. The analyzed results are used to optimize the execution of frequently executed instructions and micro operations.

A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family F of permutations on {0,1,. . . ,n-1} is min-wise independent if for any X {0,1,. . . ,n-1} and any x X, Pr[min {π(X)} = π(x)]= ||X||-1 when π is chosen uniformly at random from F, where ||A|| is the cardinality of a finite set A. We also say that a family F of permutations on {0,1,. . . ,n-1} is d-wise independent if for any distinct x1,x2,. . . ,xd {0,1,. . . , n-1} and any distinct y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i=1d π(xi) = π(yi)]= 1/{n(n-1) (n-d+1)} when π is chosen uniformly at random from F (note that nontrivial constructions of d-wise independent family F of permutations on {0,1,. . . ,n-1} are known only for d=2,3). Recently, Broder, et al. showed that any family F of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-1)}; (upper bound) Pr[min {π(X)}=π(x)] O(1/k). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any X {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)2}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).

This paper evaluates the code efficiency of the ARM, Java, and x86 instruction sets by compiling the SPEC CPU95/CPU2000/JVM98 and CaffeineMark benchmarks, from the aspects of code sizes, basic block sizes, instruction distributions, and average instruction lengths. As a result, mainly because (i) the Java architecture is a stack machine, (ii) there are only four local variables which can be accessed by a 1-byte instruction, and (iii) additional instructions are provided for the network security, the code efficiency of Java turns out to be inferior to that of ARM Thumb. Moreover, through this efficiency analysis it should be stressed that there exists the high potential of constructing a more efficient code architecture by taking minute account of the customization of an instruction set as well as the number of registers.

This paper proposes a scheme for joint synchronization between stored media with interactive control and live media in multicast communications. We deal with visual search control, such as fast-forward and fast-reverse, as interactive control. The proposed scheme enables visual search by enhancing the virtual-time rendering (VTR) media synchronization algorithm, which the authors previously proposed, and adjusts the timing of changing the visual search mode among destinations by carrying out group synchronization control. We also demonstrate the effectiveness of the scheme by experiment.

In this paper, we study loop pipeline scheduling problem under given resource assignment (operation to functional unit assignments and data to register assignments), which is one of the key tasks in data-path synthesis based on the assignment solution space exploration. We show an approach using a precedence constraint graph with parametric disjunctive arcs generated from the specified assignment information, and derive a scheduling method using branch-and-bound exploration of the parameter space. As an application of the proposed scheduling method, it is incorporated with Simulated-Annealing (SA) based exploration of assignment solution space, and it is demonstrated that data-paths of the fifth-order elliptic wave filter are successfully synthesized.

A parallel file system is normally used to support excessive file requests from parallel applications in a cluster system, whereas prefetching is useful for improving the file system performance. This paper proposes dynamic file prefetching scheme based on file access patterns, named table-comparison prefetching policy, that is particularly suitable for parallel scientific applications and multimedia web services in a VIA-based parallel file system. VIA relieves the communication overhead of traditional communication protocols, such as TCP/IP. The proposed policy introduces a table-comparison method to predict data for prefetching. In addition, it includes an algorithm to determine whether and when prefetching is performed using the current available I/O bandwidth. Experimental results confirmed that the use of the proposed prefetching policy in a VIA-based parallel file system produced a higher file system performance for various file access patterns.

We have designed the Half Adder (HA) circuit and the Carry Save Serial Adder (CSSA) circuit based on pipeline architecture. Our HA has the structure of a two-stage pipeline and consists of 160 Josephson Junctions (JJs). Our CSSA has the structure of a four-stage pipeline with a feedback loop and consists of 360 JJs. These circuits were fabricated by the NEC standard process. There are two issues which should be considered in the design. One is parameter spreads generated by the fabrication process and the other is leakage currents between the gates. We have introduced a parameter optimization method to deal with the parameter spreads. We have also inserted three stages of JTLs to reduce leakage currents. We have experimentally confirmed the correct operations of these circuits. The obtained bias margins were 33.1% for the HA and 24.6% for the CSSA.

We describe the logic design of a single-flux-quantum (SFQ) 22 unit switch. It is the main component of the SFQ Banyan packet switch we are developing that enables a switching capacity of over 1 Tbit/s. In this paper, we focus on the design of the controller in the unit switch. The controller does not have a simple "off-the-shelf" conventional circuit, like those used in shift registers or adders. To design such a complicated random logic circuit, we need to adopt a systematic top-down design approach. Using a graphical technique, we first obtained logic functions. Next, to use the deep pipeline architecture, we broke down the functions into one-level logic operations that can be executed within one clock cycle. Finally, we mapped the functions on to the physical circuits using pre-designed SFQ standard cells. The 22 unit switch consists of 59 logic gates and needs about 600 Josephson junctions without gate interconnections. We tested the gate-level circuit by logic simulation and found that it operates correctly at a throughput of 40 GHz.

A new class of least-squares algorithms is presented for adaptive filtering. The idea is to use a fixed set of directions and perform line search with one direction at a time in a cyclic fashion. These algorithms are called Euclidean Direction Search (EDS) algorithms. The fast version of this class is called the Fast-EDS or FEDS algorithm. It is shown to have O(N) computational complexity and a convergence rate comparable to that of the RLS algorithm. Computer simulations are presented to illustrate the performance of the new algorithm.

With increased size and issue-width, instruction issue queue becomes one of the most energy consuming units in today's superscalar microprocessors. This paper presents a novel architectural technique to reduce energy dissipation of adaptive issue queue, whose functionality is dynamically adjusted at runtime to match the changing computational demands of instruction stream. In contrast to existing schemes, the technique exploits a new freedom in queue design, namely the voltage per access. Since loading capacitance operated in the adaptive queue varies in time, the clock cycle budget becomes inefficiently exploited. We propose to trade-off the unused cycle time with supply voltage, lowering the voltage level when the queue functionality is reduced and increasing it with the activation of resources in the queue. Experiments show that the approach can save up to 39% of the issue queue energy without large performance and area overhead.

Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.

A novel rough neural network (RNN) structure and its application are proposed in this paper. We principally introduce its architecture and training algorithms: the genetic training algorithm (GA) and the tabu search training algorithm (TSA). We first compare RNN with the conventional NN trained by the BP algorithm in two-dimensional data classification. Then we compare RNN with NN by the same training algorithm (TSA) in functional approximation. Experiment results show that the proposed RNN is more effective than NN, not only in computation time but also in performance.

In this study, a hybrid genetic algorithm/neural network with fuzzy logic controller (NN-flcGA) is proposed to find the global optimum of reliability assignment/redundant allocation problems which should be simultaneously determined two different types of decision variables. Several researchers have obtained acceptable and satisfactory results using genetic algorithms for optimal reliability assignment/redundant allocation problems during the past decade. For large-size problems, however, genetic algorithms have to enumerate numerous feasible solutions due to the broad continuous search space. Recently, a hybridized GA combined with a neural network technique (NN-hGA) has been proposed to overcome this kind of difficulty. Unfortunately, it requires a high computational cost though NN-hGA leads to a robuster and steadier global optimum irrespective of the various initial conditions of the problems. The efficacy and efficiency of the NN-flcGA is demonstrated by comparing its results with those of other traditional methods in numerical experiments. The essential features of NN-flcGA namely, 1) its combination with a neural network (NN) technique to devise initial values for the GA, 2) its application of the concept of a fuzzy logic controller when tuning strategy GA parameters dynamically, and 3) its incorporation of the revised simplex search method, make it possible not only to improve the quality of solutions but also to reduce computational cost.

We propose a new and fast full search (FS) motion estimation algorithm for video coding. The computational reduction comes from sequential rejection of impossible candidates with derived formula and subblock norms. Our algorithm reduces more the computations than the recent fast full search (FS) motion estimation algorithms.

We propose new lossless medical image compression method based on hierarchical sorting technique. Hierarchical sorting is a technique to achieve high compression ratio by detecting the regions where image pattern varies abruptly and sorting pixel order by its value to increase predictability. In this method, we can control sorting accuracy along with size and complexity. As the result, we can reduce the sizes of the permutation-tables and reuse the tables to other image regions. Comparison using experimental implementation of this method shows better performance for medical image set measured by X-ray CT and MRI instruments where similar sub-block patterns appear frequently. This technique applies quad-tree division method to divide an image to blocks in order to support progressive decoding and fast preview of large images.

This paper describes glyph representation, that is, shape representation of inheritance relationships between a superclass and subclasses in an object-oriented programming language. The inheritance relationships in object-oriented programming languages are usually represented in a visual programming environment by a diagram of a tree graph or a nested structure. That diagram is not integrated with a code view showing control and data flows. Using the proposed representation, one can understand the inheritance relationships of classes and the assignment compatibility or type conformance just by seeing the glyphs. One thus does not need to look at a hierarchy diagram in order to recognize them. The inheritance relationships are represented by inclusion relationships of glyphs. Methods for generating suitable glyphs from a class hierarchy are also described, as is a prototype system for glyph generation. Experiments using the Java 2 Standard Edition (J2SE), which has more than 1,500 classes, show that one can recognize inheritance relationships in the proposed representation faster than in the usual textual representation. Consequently the proposed representation can facilitate the understanding of inheritance in visual object-oriented programming environments.

In the previous work, Lampson et al. proposed an IP lookup algorithm which performs binary search on prefixes (BSP). The algorithm is attractive, even for IPv6, because of its bounded worst-case memory requirement. To achieve fast forwarding, it may need to slow down the insertion speed. Although this can be justified, the routing-table reconstruction in BSP is too time-consuming to handle the frequent route updates. In this work, we propose a fast forwarding-table construction algorithm which can accomplish more than 4,000 route updates per second. Moreover, it is simple enough to fulfill the need of fast packet forwarding. With the enhanced multiway search tree, we further reduced the depth of the tree and eliminated the pointer storage; this reduces the forwarding table size and shortens the lookup time.

This paper treats the data routing problem for fault-tolerant systolic arrays based on Triple Modular Redundancy (TMR) in mixed spatial-temporal domain. The number of logical links required in TMR systolic array is basically 9 times larger than the one for corresponding non-fault-tolerant systolic array. The link sharing is a promising method for reducing the number of physical links, which may, however, degrade the fault tolerance of TMR system. This paper proposes several robust data-routing and resource-sharing (plural data transfers share a physical link, or a data transfer and a computational task share a PE as a relay node for the former and as a processor for the latter), by which certain classes of fault tolerant property will be guaranteed. A stage and a dominated set are introduced to characterize the features of routing/resource-sharing in TMR systems, and conditions on the dominated set and their resultant fault-tolerant properties are derived.