The high throughput of the cryptographic hash function has become an important aspect of the hardware implementation of security system design. There are several methods that can be used to improve the throughput performance of MD5 design. In this paper, four types of MD5 design were proposed: MD5 iterative design, MD5 unfolding design, MD5 unfolding with 4 stages of pipelining design and MD5 unfolding with 32 stages of pipelining design. The results indicated that MD5 unfolding with 32 stages pipelining of design provides a high throughput compared with other MD5 designs. By using an unfolding transformation factor of 2, the number of cycles of MD5 design was reduced from 64 to 32. All the proposed designs were successfully designed using Verilog code and simulated using ModelSim. The throughput of MD5 unfolding with 32 stages of pipelining design was increased significantly to 137.97 Gbps, and the power of this MD5 unfolding with 32 stages of pipelining was 750.99 mW. Therefore, it is suggested that an unfolding transformation with a high performance pipelining are applied to MD5 hash function design in order to produce an embedded security system design. This paper is expected to be for improving the maximum frequency and the throughput of MD5 design. Thus, by increasing the number of stages in MD5 unfolding design, the performance of MD5 designs can be improved significantly.

<p>Recent Network on Chip (NoC) design must take the thermal issue into consideration due to its great impact on the network performance and reliability, especially for 3D NoC. In this work, we design a virtual channel based fully adaptive routing algorithm for the runtime 3D NoC thermal-aware management. To improve the network throughput and latency, we use two virtual channels for each horizontal direction and design a routing function which can not only avoid deadlock and livelock, but also ensure high adaptivity and routability in the throttled network. For path selection, we design a strategy that takes priority to the distance, but also considers path diversity and traffic state. For throttling information collection, instead of transmitting the topology information of the whole network, we use a 12 bits register to reserve the router state for one hop away, which saves the hardware cost largely and decreases the network latency. In the experiments, we test our proposed routing algorithm in different states with different sizes, and the proposed algorithm shows better network latency and throughput with low power compared with traditional algorithms.</p>

The thermal problem is a challenge in recent Network on Chip (NoC) designs due to its great impact on the network performance and reliability, especially for 3D NoC. In this work, we design a virtual channel based fully adaptive routing algorithm for the runtime 3D NoC thermal-aware management. For throttling information collection, instead of transmitting the topology information of the whole network, we use a 12 bits register to reserve the router state for one hop away instead of transmitting the topology information of the whole network. It saves the hardware cost largely and decreases the network latency. To ensure deadlock and livelock free and minimize the hardware overhead, we only use two virtual channels for each horizontal channel to achieve full adaptivity and high routability. For path selection, we design a strategy that takes priority to the distance, but also consider path diversity and traffic state. Experimental results show that the proposed algorithm shows better network latency and throughput with low power compared with traditional algorithms.

In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.

In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.

As the semiconductor technology continues to develop, hundreds of cores will be deployed on a single die in the future Chip-Multiprocessors (CMPs) design. Three-Dimensional Network-on-Chips (3D NoCs) has become an attractive solution which can provide impressive high performance. An efficient and deadlock-free routing algorithm is a critical to achieve the high performance of network-on-chip. Traditional methods based on deterministic and turn model are deadlock-free, but they are unable to distribute the traffic loads over the network. In this paper, we propose an efficient, adaptive and deadlock-free algorithm (EAR) based on a novel routing selection strategy in 3D NoC, which can distribute the traffic loads not only in intra-layers but also in inter-layers according to congestion information and path diversity. Simulation results show that the proposed method achieves the significant performance improvement compared with others.

Recently, due to the development of design and manufacturing technologies for VLSI systems, an embedded system becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, a partially reconfigurable device is promising. In this paper, we propose an efficient data structure to manage the reconfigurable units. And then, on the assumption that each task utilizes the rectangle shaped resources, a very simple MER enumeration algorithm based on this data structure is proposed. By utilizing the result of MER enumeration, the free space on the reconfigurable device can be used suffi-ciently. We analyze the complexity of the proposed algorithm and confirm its efficiency by experiments.

© 2006-2016 Asian Research Publishing Network (ARPN).Hash Function is widely used in the protocol scheme. In this paper, the design of SHA-1 hash function by using Verilog HDL based on FPGA is studied to optimise both hardware resource and performance. It was successfully synthesised and implemented using Altera Quartus II Arria II GX: EP2AGX45DF29C4. In this paper, two types of design are proposed, namely SHA-1 and SHA-1unfolding. The maximum frequency of SHA-1 design is 274.2 MHz which is higher than SHA-1 unfolding that has the maximum frequency of only 174.73 MHz. However, this leads to a high throughput of the SHA1 unfolding design with 2236.54 Mbps. Besides, both designs provide a small area implementation on Arria II that requires only 423 and 548 Combinational ALUTs, 693 and 907 total register respectively.

Recently, due to the development of design and manufacturing technologies for VLSI systems, an embedded system becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, a partially reconfigurable device is promising. In this paper, we propose an efficient data structure to manage the reconfigurable units. And then, on the assumption that each task utilizes the rectangle shaped resources, a very simple MER enumeration algorithm based on this data structure is proposed. By utilizing the result of MER enumeration, the free space on the reconfigurable device can be used sufficiently. We analyze the complexity of the proposed algorithm and confirm its efficiency by experiments.

As the semiconductor technology continues to develop, hundreds of cores will be deployed on a single die in the future Chip-Multiprocessors (CMPs) design. Three-Dimensional Network-on-Chips (3D NoCs) has become an attractive solution which can provide impressive high performance. An efficient and deadlock-free routing algorithm is a critical to achieve the high performance of network-on-chip. Traditional methods based on deterministic and turn model are deadlock-free, but they are unable to distribute the traffic loads over the network. In this paper, we propose an efficient, adaptive and deadlock-free algorithm (EAR) based on a novel routing selection strategy in 3D NoC, which can distribute the traffic loads not only in intra-layers but also in inter-layers according to congestion information and path diversity. Simulation results show that the proposed method achieves the significant performance improvement compared with others.

Thermal problem is an essential issue which must be taken Into account in the 3D Network-on-Chip NoC) design, because it has a great impact on not only the network performance, but also the reliability of the message transmission. Tn this work, we prescnt a fully adaptive runtime thermal-aware routing algorithm, which combines the distance, traffic state, path dhersity and the thermal impact in the path determination. By simultaneously considering all these factors, the routing algorithm can effectively balance the traffic load while keeping high adaptivity and routability, which also results in an even distribution of temperature across the network. Instead of collecting the topology information of the whole network, we utilize a 12 bits register to reserve the router state for one hop away, which saves the hardware cost largely and decreases the network latency. The simulation results show our proposed routing algorithm can improve the latency and energy consumption by comparing with other previously proposed thermal-aware routing schemes, and the improvement is more remarkable in large scale networks.

This paper proposes a minimal adaptive routing algorithm for Network-on-Chip, which takes congestion information and routing diversity into consideration. Congestion is one of the most important factors on performance. Our algorithm can select a lower latency path for packet transmission according to the following conditions: the free buffer size of two neighbor routers is compared, the direction which has more different paths to the destination is chosen, it decides which direction the packet more tend to be transmitted by the position of the source and destination. As the result, the algorithm gets the proper direction for the next step. Comparing to other algorithms, our proposed routing algorithm has less latency and better throughput.

Escape routing is one of key problems in design of printed circuit boards (PCB), and it becomes more and more difficult for manual design due to increased pin count. This paper proposed an algorithm using an unified model to formulate the problem of escape routing of differential pairs together with single signals (mixed-pattern signals) on staggered pin array (SPA) considering the routing's density.

In modern VLSI designs, a flip-chip package is widely used to meet the higher integration density and the larger I/O counts of circuits. Recently the I/O buffers are mapped onto bump balls without changing the module placement using re-distribution layer (RDL) in flip-chip designs. In this research, a sorting-based I/O connection assignment and non-Manhattan RDL routing method is proposed for area I/O flip-chip designs. The approach initially assigns the I/O buffers to bump balls by sorting the Manhattan distance between them. Three kinds of pair-exchange procedures are then carried out to improve the initial assignment. Then to shorten the wire length, non-Manhattan RDL routing is adopted to connect the I/O buffers and bump balls. Finally some un-routed connections are ripped up and rerouted. The experimental results show that the proposed method is able to obtain the routes with shorter wire length in reasonable CPU times.

In recent printed circuit board (PCB) design, due to the high density of integration, the signal propagation delay or skew has become an important factor for a circuit performance. As the routing delay is proportional to the wire length, the controllability of the wire length is usually focused on. In this research, a heuristic algorithm to get equal-length routing for disordered pins in PCB design is proposed. The approach initially checks the longest common subsequence of source and target pin sets to assign layers for pins. Single commodity flow is then carried out to generate the base routes. Finally, considering target length requirement and available routing region, R-flip and C-flip are adopted to adjust the wire length. The experimental results show that the proposed method is able to obtain the routes with better wire length balance and smaller worst length error in reasonable CPU times.

With rapid progress in semiconductor technology, Network-on-Chip (NoC) becomes an attractive solution for future systems on chip (SoC). The network performance depends critically on the performance of packets routing. The delay of router and packets contention can significantly affect network latency and throughput. As the network becomes more congested, packets will be blocked more frequently. It would result in degrading the network performance. In this article, we propose an innovative dual-switch allocation (DSA) design. By introducing DSA design, we can make utmost use of idle output ports to reduce packets contention delay, meanwhile, without increasing router delay. Experimental results show that our design significantly achieves the performance improvement in terms of throughput and latency at the cost of very little power and area overhead.

With rapid progress in semiconductor technology, Network-on-Chip (NoC) becomes an attractive solution for future systems on chip (SoC). The network performance depends critically on the performance of packets routing. The delay of router and packets contention can significantly affect network latency and throughput. As the network becomes more congested, packets will be blocked more frequently. It would result in degrading the network performance. In this article, we propose an innovative dual-switch allocation (DSA) design. By introducing DSA design, we can make utmost use of idle output ports to reduce packets contention delay, meanwhile, without increasing router delay. Experimental results show that our design significantly achieves the performance improvement in terms of throughput and latency at the cost of very little power and area overhead.

Network-on-Chip (NoC) is an attractive solution for future systems on chip (SoC). The network performance depends critically on the performance of packets routing. However, as the network becomes more congested, packets will be blocked more frequently. It would result in degrading the network performance. In this article, we propose an innovative dual-switch allocation (DSA) design. By introducing two switch allocations, we can make utmost use of idle output ports. Experimental results show that our design significantly achieves the performance improvement in terms of throughput and latency at the cost of very little power overhead.

In this paper, for the disordered pins in printed circuit board (PCB) design, a heuristics algorithm is proposed to obtain a length matching routing. We initially check the longest common subsequence of pin pairs to assign layers for pins. Then, adopt single commodity flow to generate base routes. R-flip and C-flip are finally carried out to adjust the wire length. The experiments show that our algorithm generates the optimal routes with better wire balance within reasonable CPU times.

Modern embedded systems favor the chip multiprocessor frame to achieve higher performance, but they are restricted by the inefficient cache hierarchies. Typically, the accessing interference and improper allocation in last-level cache (LLC) shared by multiprocessors cause significant energy consumption and performance depression. In this paper, we propose a configurable and partitioned cache hierarchy where an energy-efficient runtime mechanism can well manage the shared LLC to meet application programs. This mechanism utilizes the repeated behaviors in hot subroutines of application and selects the proper partition intervals. Then, a low-power metric based configurable scheme is employed to explore the optimal allocation of given cache resources. Thus, we can provide each core with the optimal allocation information to dynamically partition the shared LLC during runtime. Experimental results for a quad-core system using the SPEC2006 benchmarks show that the cache access energy can be reduced by on average 32.5 percent compared to the equal partition scheme only with 1.3 percent performance off.

In this paper, a new deadlock-free dynamic turn model named VMCD (vertical-mesh-conscious-dynamic) is proposed for higher performance in 3D NoC. On vertical meshes and odd horizontal meshes, odd-even turn model is applied, while xy routing is utilized on even horizontal meshes. According to the priority of vertical meshes and horizontal meshes, two VMCD routing algorithms are applied based on this turn model. Compared with the Z-odd-even (ZOE) and balanced-odd-even (BOE), the proposed VMCD algorithms take adaptiveness and network balance into account simultaneously and show better performance including average latency and throughput. Compared to ZOE on 8*8*2 and 8*8*4 mesh, the improvement of throughput can be up to 68.5% and 9.3% respectively for the random traffic and 14.3% and 20% respectively for the transpose traffic pattern. The performance improvement is much more remarkable compared with BOE routing algorithm.

As the technology of semiconductor continues to develop, hundreds of cores will be deployed on a signal die in the future Chip-Multiprocessors (CMPs) design. So Three Dimensional Network-on-Chips (3D NoCs) has become an attractive solution which can provide high performance. The network performance depends critically on the performance of routing algorithm. This paper proposes a novel adaptive routing in 3D NoC which can solve congestion not only in the intra-layers but also in inter-layers. Simulation results shoo that our proposed method significantly achieves the performance improvement compared with other transitional routing algorithms.

Recently RDLs (Re-Distribution Layers) and microbumps are widely adopted in 3D IC designs. In this research, a sorting-based micro-bump assignment method is proposed. The approach initially assigns the I/O pads to micro-bumps by sorting the Manhattan distance between them. Then single layer routing in two RDLs are carried out respectively. The experimental results show that the proposed method is able to obtain the routes with shorter total wire length in reasonable CPU times.

In modern embedded systems, improving accuracy in branch prediction is one of the most crucial preoccupations. It's well known that branch alias has become one of the most serious problem that affects the accuracy in 2-level adaptive predictor. In this paper, we propose a stack-based solution which can alleviate alias problem significantly and improve the accuracy in branch prediction. Our proposed solution extends 4 bits on the conventional PHT's higher bits. Experiments are carried on Simple-scalar3.0e and the performance is verified by testing SPEC2006. The result shows that contrasting to the conventional prediction, the new proposed structure can achieve about 10.5% improvement on IPC on average with negligible extra hardware cost.

With rapid progress in Integrated Circuit technologies, Three-Dimensional Network-on-Chips (3DNoCs) have become a promising solution for achieving low latency and low power. Under the constraint of the TSV number used in 3DNoCs, designing a proper routing algorithm with fewer TSVs is a critical problem for network performance improvement. In this work, we design a novel fully adaptive routing algorithm in 3D NoC. The algorithm consists of two parts: one is a vertical node assignment in inter-layer routing, which is a TSV selection scheme in a limited quantity of TSVs in the NoC architecture, and the other is a 2D fully adaptive routing algorithm in intra-layer routing, which combines the optimization of routing distance, network traffic condition and diversity of the path selection. Simulation results show that our proposed routing algorithm can achieve lower latency and energy consumption compared with other traditional routing algorithms.

With rapid progress in Integrated Circuit technologies, Three-Dimensional Network-on-Chips (3DNoCs) have become a promising solution for achieving low latency and low power. Under the constraint of the TSV number used in 3DNoCs, designing a proper routing algorithm with fewer TSVs is a critical problem for network performance improvement. In this work, we design a novel fully adaptive routing algorithm in 3D NoC. The algorithm consists of two parts: one is a vertical node assignment in inter-layer routing, which is a TSV selection scheme in a limited quantity of TSVs in the NoC architecture, and the other is a 2D fully adaptive routing algorithm in intra-layer routing, which combines the optimization of routing distance, network traffic condition and diversity of the path selection. Simulation results show that our proposed routing algorithm can achieve lower latency and energy consumption compared with other traditional routing algorithms.

With rapid progress in Integrated Circuit technologies, Three-Dimensional Network-on-Chips (3DNoCs) have become a promising solution for achieving low latency and low power. Under the constraint of the TSV number used in 3DNoCs, designing a proper routing algorithm with fewer TSVs is a critical problem for network performance improvement. In this work, we design a novel fully adaptive routing algorithm in 3D NoC. The algorithm consists of two parts: one is a vertical node assignment in inter-layer routing, which is a TSV selection scheme in a limited quantity of TSVs in the NoC architecture, and the other is a 2D fully adaptive routing algorithm in intra-layer routing, which combines the optimization of routing distance, network traffic condition and diversity of the path selection. Simulation results show that our proposed routing algorithm can achieve lower latency and energy consumption compared with other traditional routing algorithms.

In this paper, we propose a fixed-length routing method in Printed Circuit Board (PCB). The proposed method utilizes the simpath algorithm with a randomized graph reduction. It outputs the routing of the nets with small length-error. Its efficiency is confirmed empirically.

With the progress of 3D IC integration technologies, the application of 3D Networks-on-chip (NoCs) has been proposed as a scalable and efficient solution to the global communication in the interconnect designs. In this work, we propose a new procedure for designing application specific irregular 3D NoC architectures. This procedure does not only satisfy the variability of the highly customized SoC designs, but also achieve significant performance improvement. The objective is to improve both communication latency and power consumption under several 3D constraints. A Genetic Algorithm (GA) based efficient algorithm is applied to optimize both the topology and floorplan. Numerical experiments are implemented on standard benchmarks by comparing the method application in 3D architectures with the 2D designs and then comparing the architecture obtained by our proposed algorithm with both classical topologies and custom based topologies. The experimental results show that the architectures by our design algorithm can achieve more performance improvement than other algorithms and the proposed algorithm also proves to be a time efficient method for exploration in the large solution space. © 2013 Information Processing Society of Japan.

With the progress of 3D IC integration technologies, the application of 3D Networks-on-chip (NoCs) has been proposed as a scalable and efficient solution to the global communication in the interconnect designs. In this work, we propose a new procedure for designing application specific irregular 3D NoC architectures. This procedure does not only satisfy the variability of the highly customized SoC designs, but also achieve significant performance improvement. The objective is to improve both communication latency and power consumption under several 3D constraints. A Genetic Algorithm (GA) based efficient algorithm is applied to optimize both the topology and floorplan. Numerical experiments are implemented on standard benchmarks by comparing the method application in 3D architectures with the 2D designs and then comparing the architecture obtained by our proposed algorithm with both classical topologies and custom based topologies. The experimental results show that the architectures by our design algorithm can achieve more performance improvement than other algorithms and the proposed algorithm also proves to be a time efficient method for exploration in the large solution space.

large power consumption of memory access has been one of the major bottlenecks in modern embedded systems. Because caches even take about half of those systems' power consumption. So it is essential in concentrating on optimized strategies for cache's parameters as well as the enhancement of its adaptability to various applications. Considering the particular applications of embedded systems, we can optimize the caches with configuration parameters such as cache size, line size or associativity. In this paper, we firstly put forward the relations between those cache parameters, and the quantified results establish a new reconfigurable cache structure so as to find the optimal cache parameters rapidly by a searching algorithm. Furthermore, the possible hardware implementation with certain parameters is described, and the effectiveness of this method is verified by experiments using CACTI6.5 and SPEC2006 benchmark on Simple- scalar 3.0e. Experimental results show that the proposed cache can reduce the power consumption to 38.4% of its maximum power consumption caused by the redundant hardware resources.

In recent PCB systems, the routing for high speed board is still achieved manually. As IC technology advances rapidly, the dimensions of packages and PCBs are decreasing while the pin counts and routing layers keep increasing. In this research, a parallel routing method for fixed pins using virtual boundary is proposed, which partitions the routing area into several sub-areas and routes them separately. Applying this proposed method, the wire length can be reduced. Moreover, considering the length-matching constraints, especially for the isometric wires routing problems, the proposed method can get better wire shape resemblance.

In this work, we present an efficient fully adaptive fault-tolerant routing algorithm for 3D Network-on-Chip (3D NoC). The crucial algorithm for path routing is firstly routing the packet to the destination layer by using an adaptive vertical node assignment scheme in the NoC architecture with a limited quantity of TSVs and then routing to the destination node within the 2D layer through a fully adaptive routing algorithm. Instead of rerouting packets around the fault regions when fault occurs, our proposed algorithm applies a fault detection scheme which can get the fault information one hop away in advance, and it combines the fault information when doing the path computation. This algorithm can deal with multi faults in the 3D NoC architecture. Simulation results show that our proposed routing algorithm can achieve lower latency, energy consumption and higher packet arrival rate compared with other traditional routing algorithms in various network applications.

As the technology of chip multiprocessors (CMPs) is evolved, the performance of 2D architecture becomes insufficient to meet various requirements, and three-dimensional integrated circuits (3D-ICs) provide an attractive solution to improve network performance by using through silicon via (TSV). However, there are more transmitted packets in 3D network and congestion condition becomes more complex. The performance of network depends critically on its routing algorithm. Various routing algorithms have been proposed for 3D NoCs. Adaptive routing algorithm that merges local congestion and future congestion information was proposed in [9]. But the congestion used in it is roughly estimated, not very precise, but network performance is affected by the congestion significantly. In this paper, we propose a more precise congestion for predictor based on [9] and implement it in 3D NoCs. The proposed method is proved to have better latency and throughput than traditional routing methods like XY routing and Odd-even routing.

Dynamic power gating applicable to FPGA can reduce the power consumption effectively. In this paper, we propose a sophisticated routing architecture for a region oriented FPGA which supports dynamic power gating. This is the first routing solution of dynamic power gating for coarse-grained FPGA. This paper has 2 main contributions. First, it improves the routing resource graph and routing architecture to support special routing for a region oriented FPGA. Second, some routing channels are made wider to avoid congestion. Experimental result shows that 7.7% routing area can lie reduced compared with the symmetric Wilton switch box in the region. Also, our proposed FPGA architecture with sophisticated P&R can reduce the power consumption of the system implemented in FPGA.

An FPGA plays an essential role in industrial products due to its fast, stable and flexible features. But the power consumption of FPGAs used in portable devices is one of critical issues. Top-down hierarchical design method is commonly used in both ASIC and FPGA design. But, in the case where plural modules are integrated in an FPGA and some of them might be in sleep-mode, current FPGA architecture cannot be fully effective. In this paper, coarse-grained power gating FPGA architecture is proposed where a whole area of an FPGA is partitioned into several regions and power supply is controlled for each region, so that modules in sleep mode can be effectively power-off. We also propose a region oriented FPGA placement algorithm fitted to this user's hierarchical design based on VPR [1]. Simulation results show that this proposed method could reduce power consumption of FPGA by 38% on average by setting unused modules or regions in sleep mode.

Modern embedded processors commonly use a set-associative scheme to reduce cache misses. However, a conventional set-associative cache has its drawbacks in terms of power consumption because it has to probe all ways to reduce the access time, although only the matched way is used. The energy spent in accessing the other ways is wasted, and the percentage of such energy will increase as cache associativity increases. Previous research, such as phased caches, way prediction caches and partial tag comparison, have been proposed to reduce the power consumption of set-associative caches by optimizing the cache access mode. However, these methods are not adaptable according to the program behavior because of using a single access mode throughout the program execution. In this paper, we propose a behavior-based adaptive access-mode for set-associative caches in embedded systems, which can dynamically adjust the access modes during the program execution. First, a program is divided into several phases based on the principle of program behavior repetition. Then, an off-system pre-analysis is used to exploit the optimal access mode for each phase so that each phase employs the different optimal access mode to meet the application's demand during the program execution. Our proposed approach requires little hardware overhead and commits most workload to the software, so it is very effective for embedded processors. Simulation by using Spec 2000 shows that our proposed approach can reduce roughly 76.95% and 64.67% of power for an instruction cache and a data cache, respectively. At the same time, the performance degradation is less than 1%.Modern embedded processors commonly use a set-associative scheme to reduce cache misses. However, a conventional set-associative cache has its drawbacks in terms of power consumption because it has to probe all ways to reduce the access time, although only the matched way is used. The energy spent in accessing the other ways is wasted, and the percentage of such energy will increase as cache associativity increases. Previous research, such as phased caches, way prediction caches and partial tag comparison, have been proposed to reduce the power consumption of set-associative caches by optimizing the cache access mode. However, these methods are not adaptable according to the program behavior because of using a single access mode throughout the program execution. In this paper, we propose a behavior-based adaptive access-mode for set-associative caches in embedded systems, which can dynamically adjust the access modes during the program execution. First, a program is divided into several phases based on the principle of program behavior repetition. Then, an off-system pre-analysis is used to exploit the optimal access mode for each phase so that each phase employs the different optimal access mode to meet the application's demand during the program execution. Our proposed approach requires little hardware overhead and commits most workload to the software, so it is very effective for embedded processors. Simulation by using Spec 2000 shows that our proposed approach can reduce roughly 76.95% and 64.67% of power for an instruction cache and a data cache, respectively. At the same time, the performance degradation is less than 1%.

Current trends in modern out-of-order processors involve implementing deeper pipelines and a large instruction window to achieve high performance, which lead to the penalty of the branch misprediction recovery being a critical factor in overall processor performance. Multi path execution is proposed to reduce this penalty by executing both paths following a branch, simultaneously. However, there are some drawbacks in this mechanism, such as design complexity caused by processing both paths after a branch and performance degradation due to hardware resource competition between two paths. In this paper, we propose a new recovery mechanism, called Recovery Critical Misprediction (RCM), to reduce the penalty of branch misprediction recovery. The mechanism uses a small trace cache to save the decoded instructions from the alternative path following a branch. Then, during the subsequent predictions, the trace cache is accessed. If there is a hit, the processor forks the second path of this branch at the renamed stage so that the design complexity in the fetch stage and decode stage is alleviated. The most contribution of this paper is that our proposed mechanism employs critical path prediction to identify the branches that will be most harmful if mispredicted. Only the critical branch can save its alternative path into the trace cache, which not only increases the usefulness of a limited size of trace cache but also avoids the performance degradation caused by the forked non-critical branch. Experimental results employing SPECint 2000 benchmark show that a processor with our proposed RCM improves IPC value by 10.05% compared with a conventional processor.

Since the power consumption of FPGA is larger than that of ASIC under the condition to perform the same function using the same scaling, the application of FPGA is limited especially in portable electronic devices. In this paper, we propose a novel low-power FPGA architecture based on coarse-grained power gating to reduce power consumption. The new placement algorithm and routing resource graph for sleep regions is also presented. After enhancing the CAD framework, a detailed discussion is given under different region size supported by the new FPGA architecture. As a result, our proposed FPGA architecture combined with the new placement and routing algorithm can reduce 19.4% in the total power consumption compared with the traditional FPGA. By using our proposed method, FPGA is promising to be widely applied to portable devices.

Modern microprocessors employ caches to bridge the great speed variance between a main memory and a central processing unit, but these caches consume a larger and larger proportion of the total power consumption. In fact, many values in a processor rarely need the full-bit dynamic range supported by a cache. The narrow-width value occupies a large portion of the cache access and storage. In view of these observations, this paper proposes an Adaptive Various-width Data Cache (AVDC) to reduce the power consumption in a cache, which exploits the popularity of narrow-width value stored in the cache. In AVDC, the data storage unit consists of three sub-arrays to store data of different widths. When high sub-arrays are not used, they are closed to save its dynamic and static power consumption through the modified high-bit SRAM cell. The main advantages of AVDC are: 1) Both the dynamic and static power consumption can be reduced. 2) Low power consumption is achieved by the modification of the data storage unit with less hardware modification. 3) We exploit the redundancy of narrow-width values instead of compressed values, thus cache access latency does not increase. Experimental results using SPEC 2000 benchmarks show that our proposed AVDC can reduce the power consumption, by 34.83% for dynamic power saving and by 42.87% for static power saving on average, compared with a cache without AVDC.

Power consumption has become an increasing concern in high performance microprocessor design. Especially, Instruction Cache (I-Cache) contributes a large portion of the total power consumption in a microprocessor, since it is a complex unit and is accessed very frequently. Several studies on low-power design have been presented for the power-efficient cache design. However, these techniques usually suffer from the restrictions in the traditional Instruction Fetch Unit (IFU) architectures where the fetch address needs to be sent to I-Cache once it is available. Therefore, work to reduce the power consumption is limited after the address generation and before starting an access. In this paper, we present a new power-aware IFU architecture, named Analysis Before Starting an Access (ABSA), which aims at maximizing the power efficiency of the low-power designs by eliminating the restrictions on those low-power designs of the traditional IFU. To achieve this goal, ABSA reorganizes the IFU pipeline and carefully assigns tasks for each stages so that sufficient time and information can be provided for the low-power techniques to maximize the power efficiency before starting an access. The proposed design is fully scalable and its cost is low. Compared to a conventional IFU design, simulation results show that ABSA saves about 30.3% fetch power consumption, on average. I-Cache employed by ABSA reduces both static and dynamic power consumptions about 85.63% and 66.92%, respectively. Meanwhile the performance degradation is only about 0.97%.

This paper proposes a new circuit design optimization method where Genetic Algorithm (GA) with parameterized uniform crossover (GApuc) is combined with Taguchi method. The purposed are (a) using Taguchi method to search for optimal fitness value and (b) evaluating the power and signal delay of logic blocks in circuit design to get an optimum circuit in complexity, power and signal delay. The present study enhances the previous results by providing a much more detailed examination of mixed constrained circuit design. Experimental results show that our proposed approach can produce a good circuit in both fitness function and CPU time. © 2011 IEEE.

This paper describes mixed constrained image filter design with fault tolerant using Particle Swarm Optimization (PSO) on a reconfigurable processing array. There may be some faulty Configurable Logic Blocks (CLBs) in a reconfigurable processing array. The proposed method with PSO autonomously synthesizes a filter fitted to the reconfigurable device with some faults, to optimize the complexity and power of a circuit, and signal delay in both CLBs and wires. An image filter for noise reduction is experimentally synthesized to verify the validity of our method. By evolution, the quality of the optimized image filter on a reconfigurable device with a few faults is almost same as that with no fault.

This paper describes a high performance neural processor by using a Network on Chip (NoC) architecture to solve the interconnection and performance problems in hardware neural networks. The proposed NoC-based neural processor is composed of 20 tiles in 4x5 2-D array, and each tile includes a Process Element (PE) and a packet switched router. In each PE, four neurons are implemented to achieve low communication load. The network is 2-D torus topology, and it has a 32 G/s bandwidth and asynchronous clocking system. Our proposed neural processor is designed using 90-nm CMOS technology with one Poly and nine metals, and its performance is evaluated. As a result, it can achieve over 3.1 G Connection Per Second (CPS) of performance while power dissipation is 1.1317 W at 1.2 V supply-voltage and 25 mm(2) chip area. Compared with the other existing hardware neural networks, the proposed processor can achieve low communication load and high performance, and it is reconfigurable and extendable.

Multiple power domain design architectures have been studied for the power-efficient FPGAs. But, most of these researches pay attention on the clustered logic block's finegrain power gating which increases the FPGA size significantly. This paper presents a fast placement algorithm for coarsegrain FPGAs architecture, by which the circuit with multiple power domains is mapped into several regions for low power consumption. Each region uses one or several sleep transistors in order to conserve leakage energy. Using the CAD framework, we discuss the power efficiency of sleep region FPGA architecture by using the benchmarks assumed in multiple power domains. Simulation result shows that 9.1% power consumption of FPGA can be reduced on average by the proposed placement algorithm, compared to the traditional algorithm. Furthermore, when the dual power domains are individually power-on and -off, our proposed method can reduce the power more than 20%. © 2011 IEEE.

The application of 3D Networks-on-chip (NoCs) has been proved to be an effective solution to the global communication of 3D IC integration, while the design of NoC topologies has played a critical role to increase interconnection performance. In this work, we propose a new procedure for designing application specific irregular 3D NoC topologies which achieve significant performance improvement. The objective is to improve both communication latency and power consumption under several 3D constraints. We propose a two-stage design model based on a series of efficient algorithms to explore the optimized topology in a large scale searching space. Numerical experimental results show that the topologies by our design algorithm achieve more performance improvement (about 31.5%) than the classical topologies and the proposed algorithm also proves to be a time efficient method for exploration in the large solution space. © 2011 IEEE.

Hardware implementation methods for Artificial Neural Network (ANN) have been researched for a long time to achieve high performance. We have proposed a Network on Chip (NoC) for ANN, and this architecture can reduce communication load and increase performance when an implemented ANN is small. In this paper, a multiple NoC models are proposed for ANN, which can implement both a small size ANN and a large size one. The simulation result shows that the proposed multiple NoC models can reduce communication load, increase system performance of connection-per-second (CPS), and reduce system running time compared with the existing hardware ANN. Furthermore, this architecture is reconfigurable and reparable. It can be used to implement different applications of ANN.

Evolvable hardware (EHW) is a new research field about the use of Evolutionary Algorithms (EAs) to construct electronic systems. EHW refers in a narrow sense to use evolutionary mechanisms as the algorithmic drivers for system design, while in a general sense to the capability of the hardware system to develop and to improve itself. Genetic Algorithm (GA) is one of typical EAs. We propose optimal circuit design by using GA with parameterized uniform crossover (GApuc) and with fitness function composed of circuit complexity, power, and signal delay. Parameterized uniform crossover is much more likely to distribute its disruptive trials in an unbiased manner over larger portions of the space, then it has more exploratory power than one and two-point crossover, so we have more chances of finding better solutions. Its effectiveness is shown by experiments. From the results, we can see that the best elite fitness, the average value of fitness of the correct circuits and the number of the correct circuits of GApuc are better than that of GA with one-point crossover or two-point crossover. The best case of optimal circuits generated by GApuc is 10.18% and 6.08% better in evaluating value than that by GA with one-point crossover and two-point crossover, respectively.

This article describes an evolutionary image filter design for noise reduction using particle swarm optimization (PSO), where mixed constraints on the circuit complexity, power, and signal delay are optimized. First, the evaluated values of correctness, complexity, power, and signal delay are introduced to the fitness function. Then PSO autonomously synthesizes a filter. To verify the validity of our method, an image filter for noise reduction was synthesized. The performance of the resultant filter by PSO was similar to that of a genetic algorithm (GA), but the running time of PSO is 10% shorter than that of GA. © 2010 International Symposium on Artificial Life and Robotics (ISAROB).

This article describes an evolutionary image filter design for noise reduction using particle swarm optimization (PSO), where mixed constraints on the circuit complexity, power, and signal delay are optimized. First, the evaluated values of correctness, complexity, power, and signal delay are introduced to the fitness function. Then PSO autonomously synthesizes a filter. To verify the validity of our method, an image filter for noise reduction was synthesized. The performance of the resultant filter by PSO was similar to that of a genetic algorithm (GA), but the running time of PSO is 10% shorter than that of GA. © 2010 International Symposium on Artificial Life and Robotics (ISAROB).

Hardware implementation of Artificial Neural Network (ANN) is proposed by using Networks on Chip (NoC) with 5-port 2-virtual channels router, aiming at higher performance and low latency. Experimental results by NIRGAM NoC simulator show that this proposed system has higher Connection-Per-Second (CPS), higher Connection-Per-Second-Per-Weight (CPSPW), lower communication load. Furthermore this NoC implementation system is reconfigurable and expandable, so that it can be applied to various applications.

Recently, a Network on Chip (NoC) has attracted much attention for its smart structure and high performance. However, NoC routing algorithms significantly influences the performance and design cost. In this paper, a new hardware method to implement a routing algorithm is proposed. The proposed method is used to replace the general destination-tag method for router design. We simulate and evaluate the router and NoC with proposed method in terms of circuit resource, latency and throughput. The results indicate that the NoC architecture with proposed method is effective in reducing circuit resource, latency and increasing throughput. © 2010 IEEE.

Hardware implementation by Networks on Chip (NoC) for Artificial Neural Network (ANN) was proposed to improve. In this work, a new architecture of NoC which has a hardware implementation of routing algorithm is proposed for ANN design. This routing strategy could reduce the packet size of header. The NOXIM NoC simulator is used to simulate the proposed system in term of latency, throughput and power consumption. The experimental results indicate that the proposed new NoC architecture is effective in increasing throughput and reducing latency and power consumption, compare with the traditional one. The ANN with the new NoC architecture could achieve higher performance and lower communication load.

Reducing the power consumption is one of the most important design problems at present. Modern microprocessors employ caches to bridge the great speed variance between the main memory and the central processing unit, but these caches propose larger and larger proportion in the total power consumption. In fact, many values rarely need the full-bit dynamic range supported by a cache. The Narrow-Width Value (NWV) occupies a large portion of cache access and storage. It is unreasonable that the storage space for value of any data width is the same in the cache, even if NWV needs only a few bits to be stored. This paper proposes a Variable Bitline Data Cache (VBDC) which exploits the popularity of NWV stored in the cache. In VBDC design, the cache data array is divided into several sub-arrays to adapt each data pattern with the different bitline length to access. The VBDC can shut off the corresponding unused high arrays to reduce its dynamic and static power consumption. The VBDC achieves low power consumption through reducing the bitline length. Experimental results employing SPEC 2000 benchmarks show that our proposed VBDC can reduce both the dynamic power consumption ant the static power consumption by 44.75% and 42.86%.

This paper describes mixed constrained image filter design with fault tolerant using Genetic Algorithm (GA) on a reconfigurable processing array. There may be some faulty Configurable Logic Blocks (CLBs) in a reconfigurable processing array at random. The proposed method with GA autonomously synthesizes a filter fitted to the reconfigurable device with some faults, evaluating the complexity, power and signal delay in both CLBs and wires. An image filter for noise reduction is experimentally synthesized to verify the validity of our method. By evolution, the quality of the optimized image filter on a reconfigurable device with a few faults is almost same as that with no fault.

Networks on Chip (NoC) has been widely discussed for its smart structure and high performance. Routing algorithms significantly influence design cost and system performance of NoC. In this paper, a new hardware method called Final-Destination-Tag (FDT) is proposed to improve the original Destination-Tag (DT) method for implementing different routing algorithms. Compared with the DT method, the proposed FDT method could reduce the header size of the packet. We evaluate NoC with this proposed method in terms of circuit resource, average latency, max latency, average throughput and power consumption. The results indicate that the proposed method is effective in increasing throughput and reducing circuit resource, latency and power consumption for NoC.

This paper presents a novel architecture for the FPGA-based implementation of multilayer neural network (NN), which integrates the layer-multiplexing and pipeline architecture together. The proposed method is aimed at enhancing the efficiency of resource usage and improving the forward speed at the module level, so that a larger NN can be implemented on commercial FPGAs. We developed a mapping method from NN schematic to physical architecture in FPGA by using the hybrid architecture, and also developed an algorithm to automatically determine the architecture by optimizing the application specific neural network topology. The experimental results with several different network topologies show that the proposed architecture can produce a very compact circuit with higher speed, compared with conventional methods.

In the traditional GA, the tournament selection for crossover and mutation is based on the fitness of individuals. This can make convergence easy, but some useful genes may be lost. In selection, as well as fitness, we consider the different structure of each individual compared with an elite one. Some individuals are selected with many different structures, and then crossover and mutation are performed from these to generate new individuals. In this way, the GA can increase diversification into search spaces so that it can find a better solution. One promising application of GA is evolvable hardware (EHW), which is a new research field to synthesize an optimal circuit. We propose an optimal circuit design by using a GA with a different structure selection (GAdss), and with a fitness function composed of circuit complexity, power, and signal delay. Its effectiveness is shown by simulations. From the results, we can see that the best elite fitness, the average fitness value of correct circuits, and the number of correct circuits with GAdss are better than with GA. The best case of optimal circuits generated by GAdss is 8.1% better in evaluation value than that by traditional GA. © 2009 International Symposium on Artificial Life and Robotics (ISAROB).

Evolvable Hardware (EHW) is a new field about the use of Evolutionary Algorithms (EA) to synthesize a circuit. Genetic Algorithm (GA) is one of the typical EA. In traditional GA, the crossover is one-point crossover or two-point crossover. One-point crossover and two-point crossover change the genes of individuals too many in one time and they are not flexible, so it may lose some useful genes. In this paper, we propose the novel cell crossover. The cell crossover can change genes more flexibly and enhance more diversification to search spaces than one-point crossover and two-point crossover, so that we can find better solution. We propose optimal circuit design by using GA with cell crossover (GAcc), and with fitness function composed of circuit complexity, power and signal delay. Simulation results show GAcc is superior to traditional GA in point of the best elite fitness, the average value of fitness of correct circuits and the number of correct circuits. The best optimal circuit generated by GAcc is 27.9% better in evaluating value than that by GA with one-point crossover.

Various hardware implementations of neural networks have been studied well in recent years. We have already proposed a hardware implementation method for neural network with a Network on Chip (NoC) architecture. A mapping of a neural network on NoC should be tuned to achieve high performance whenever neural network application is changed, so that different mapping methods are needed every time and tedious or burdensome works are required. In this paper, we propose a general mapping strategy based on three rules. The mapping method with this strategy can implement different neural networks applications with NoC architecture. The simulation results show that the proposed method makes the system low latency and high performance.

This paper describes evolutionary image filter design for noise reduction using Genetic Algorithm (GA), where the circuit complexity, power and signal delay are optimized. First, the evaluating value about correctness, complexity, power and signal delay are introduced to the fitness function. Then GA autonomously synthesizes a circuit which is simple and has good performance. To verify the effectiveness of our method, an image filter for noise reduction is experimentally synthesized. The resultant image filter by GA and the quality of filtered image are discussed.

Networks on Chip (NoC), a new packet-based design method, with a new Dependable No Deadlock (DND) backtracking routing algorithm are proposed to implement Artificial Neural Network (ANN). This system is simulated by NIRGAM NoC simulator to get system performance. Experimental results show that this proposed system has higher Connection-Per-Second (CPS), lower communication load than the exiting other implemented ANN. Furthermore this NoC implementation system is reconfigurable and expandable. In addition, this implementation method has a higher dependable than our former NoC implemented ANN system.

In modern superscalar processor, branch misprediction penalty becomes a critical factor in overall processor performance. Previous researches proposed dual (or multi) path execution methods attempt to reduce the misprediction penalty, but these methods are quite complex and high power consumption. Most of the reasons are due to simultaneously fetching and executing instructions from multiple. In this paper, we reduce branch misprediction penalties based on the balance between complexity, power, and performance. We present a novel technique-Decode Recovery Cache (DRC) - for reducing misprediction penalty, giving consideration to complexity and power consumption simultaneously. The DRC stores decoded instructions that are mispredicted. Then during subsequent mispredictions, a hit in the DRC can reduce the re-fill time of pipeline, and eliminate instruction re-fetch and its subsequent decoding. The bypassing of both re-fetching and re-decoding reduces processor power. Experimental results employing SPECint 2000 benchmark show that, using a processor with DRC, IPC value is significantly improved by 10.4% on average over the traditional processors and average power consumption is reduced by 62.6%, compared with dual Path Instruction Processing.

Reducing the power consumption is one of the most important design problems at present. Modern microprocessors employ caches to bridge the great speed variance between the main memory and the central processing unit, but these caches propose larger and larger proportion in the total power consumption. The Narrow-Width Value (NWV) occupies a large portion of cache access and storage. The storage space for value of any data width is the same in the cache, even if NWV needs only a few bits to be stored. This paper proposes an Adaptive Width Data Cache (AWDC) which exploits the popularity of NWV stored in the cache. In AWDC, the cache data array is divided into several data arrays to adapt different data width to access/store. Its purpose is shutting off corresponding unused high arrays to reduce its dynamic and static power consumption. AWDC achieves low power consumption only by the modification of the high-bit SRAM unit almost without any additional hardware, and does not affect cache performance. Experimental results employing SPEC 2000 benchmarks show that our proposed AWDC can reduce both the dynamic power consumption ant the static power consumption by 44.75% and 42.86%.

In this paper, an Artificial Autoassociative Neural Network (AANN) is implemented by Network on Chip (NoC) architecture to solve communication and performance problem. This proposed NoC based system can map four neurons in one PE and the whole system consists of PEs each of which connects with a router. This system is reconfigurable and extendable so that it can easily suit for different applications. Simulation results show that the proposed implementation method can reduce communication load and total computation time. ©2009 IEEE.

In this paper, a new fully digitized hardware design scheme of a soccer robot controller is presented as an application of a multiprocessor system. It is designed and implemented on one-chip FPGA with two embedded Nios II processors to verify the effectiveness of our system. In the practical test, the system is dependable, and has the characteristics of fast response and high precision. It also has the advantages of smaller PCB area, less chip number and shorter development period.

In this paper, a new fully digitized hardware design scheme of a soccer robot controller is presented as an application of a multiprocessor system. It is designed and implemented on one-chip FPGA with two embedded Nios II processors to verify the effectiveness of our system. In the practical test, the system is dependable, and has the characteristics of fast response and high precision. It also has the advantages of smaller PCB area, less chip number and shorter development period.

Recently, Networks-on-Chips (NoCs) have a great development and have been proposed as a promising solution to complex on-chip communication problems. One of the problems is an application of Artificial Neural Networks (ANNs). In this paper, we propose NoCs for the ANNs. NoCs is designed to implement a BP-ANNs (Back-Propagation) and evaluated by Network-on-Chips. Experimental results show that for has a great reduction in communication load and a high connection per second (CPS) compared with traditional BP-ANNs. It is also reconfigurable, expandable and stable to meet various problems.

A circuit designed by human often results in very complex hardware architectures, requiring a large amount of manpower and computational resources. A wider objective is used to find novel solutions to design such complex architectures so that system functionality and performance may not be compromised. Design automation using reconfigurable hardware and Evolutionary Algorithms (EA), such as Genetic Algorithm (GA), is one of the methods to tackle this issue. This concept applies the notion of Evolvable Hardware (EHNV) to the problem domain such as novel design solutions and circuit optimization. EHW is a new field about the use of EA to synthesize a circuit. EA manipulates a population of individuals where each individual describes how to construct a candidate for a good circuit. Each circuit is assigned a fitness, which indicates how well a candidate satisfies the design specification. EA uses stochastic operators repeatedly to evolve new circuit configurations from existing ones, and a resultant circuit configuration will exhibit a desirable behavior. In this paper, optimum circuit design by using GA with fitness function composed of circuit complexity, power and time delay is proposed, and its effectiveness is shown by simulations.

Artificial Neural Networks (ANNs) are widely used in applications of an intelligent system such as pattern recognition, fuzzy system, optimization and control. We have already proposed a novel NoC architecture for different kinds of BP-ANNs [1][2] and it was shown that the architecture is a promising hardware implementation for Neural Network. However, some problems to be solved are still remained. One of them is performance. In this paper, we propose another NoC architecture, network topology and routing strategy for higher performance. Experimental results by NoC simulator show that this new architecture and routing strategy reduce the communication load, reduce both latency by 7.7% and dynamic power consumption by 10.3% and also improve throughput by 8.1%, all compared with the previous one.

Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):
(1) G is a directed graph with two disjoint vertex sets A and B.
(2) There are r(11) (r(22), respectively) directed edges between every pair of vertices in A(B), and r(12) directed edges between every pair of vertex in A and vertex in B.
Then G is called an (r(11), r(12), r(22))-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2):
(1) G has two disjoint vertex sets A and B.
(2) For every vertex pair u, v epsilon G (u not equal v), G satisfies
[GRAPHICS]
where uv (vu, respectively) means a directed edges from u to v (from v to u).
Then G is called an (r(11),r(12),r(22))-tournament ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament "(or S is realizable) if the answer is "yes."
We proposed the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not [5]. In this paper, we propose an algorithm for constructing a "tournament" from such a score sequence pair.

Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2):
(1) G has two disjoint vertex sets A and B.
(2) For every vertex pair u, v is an element of G (u not equal v), G satisfies
vertical bar{uv}vertical bar + vertical bar{vu}vertical bar = {r(11) if u, v is an element of A {r(12) if u is an element of A, v is an element of B {r(22) if u, v is an element of B
where uv (vu, respectively) means a directed edges from u to v (from v to u).
Then G is called an (r(11),r(12),r(22))-tournamenf ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pairproblem of a "tournament", and S is called a score sequence pair of a "tournament" (or S is realizable) if the answer is "yes."
In this paper, we propose the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

Recently,a circuit complexity of VLSIs,especially SOCs(Systm-on-a-chip),has been increased more and more due to the requirements of high performance and various functions,and their layout design has become a great di cult task. So that,circuit partitioning is indispensable to an e cient and superior system design,where the whole circuit is partitioned into sub-circuits of a reasonable size. Circuit partitioning is reduced to a graph partitioning problem. But the problem is known as an NP-complete problem,even if two-way partitioning of a graph with unity node-size and edge-weight.So,we propose a hier- archical tree partitioning method,where two greedy algorithms are executed in some probability. Experimental results show that the proposed method can e ciently make a good circuit partition,and it is very useful for a VLSI design.

In this paper, we propose a fine grain Cooled Logic architecture for low-power oriented processors. Cooled Logic detects, in novel hardware method with dual-rail logic, functional blocks to be active, and stops clocks to each of the functional blocks in order to make it inactive at certain periods. To confirm the effectiveness of our approach, we design a 4-bit and a 16-bit event-driven array multipliers, and analyze their power consumption by the HSPICE simulator. As a result, it is shown that Cooled Logic has a tendency to reduce power consumptions in both the functional blocks and the clock drivers of the multipliers.

A real-valued shift-orthogonal finite-length sequence has a sharp autocorrelation function with zero sidelobes except at shift ends, and can be synthesized by element sequences. In this paper, we propose the structure of a digital matched Alter for Mary Direct Sequence Spread Spectrum (M-ary/DS-SS) system using the sequences and the reduction of operation elements of the digital matched Alter. It is shown that this digital matched Alter for M-ary/DS-SS system can be constructed by the multipliers and the adders proportional to sequence length.

This paper deals with a new low-power clocking scheme for dynamic logic circuits to reduce power dissipation. Although conventional clocking schemes for dynamic logic circuits are mainly used for high-speed applications like domino circuits, their peak-current are very large due to the concentration of precharging and discharging in a short period. It is hard for these schemes to accomplish both reductions of power dissipation and high performance at the same time. In the field of power engineering, levering power means decreasing peak-to-peak of power keeping its amount. So, we propose a sophisticated clocking scheme leveling power dissipation of processing elements that mainly reduces power dissipation of crock drivers. Our proposed clocking scheme uses an over-lapped clock with a fine-grain power control, and peak-current becomes lower and power dissipation in short period is levered without penalty of speed performance. Our proposed scheme is applied to a 4-bit array multiplier, and reductions of power dissipation of both the multiplier and clock driver are measured by the HSPICE simulator based on 0.5 mum CMOS technology. It is shown that power dissipation of clock drivers, 4-bit array multiplier, and the total are reduced by about 13.2 percent, 2.6 percent and 7.0 percent, respectively. As a result, our clocking scheme is effective in reduction of power dissipations of clock drivers.

In LSI layout design, two kinds of wire patterns are used to connect equipotential terminals. One is a so-called "ordinary routing-pattern" which is defined by line segments with a given width along a route, and another is a "polygon routing-pattern" whose shape is defined by coordinates of polygon's vertices. The latter is difficult to deal with layout CAD/DA tools like a layout compactor, because direction of wire's expansion and contraction cannot be recognized. So, we propose an algorithm which can efficiently transform a polygon routing-pattern into an ordinary one, by constructing a routing tree connecting terminals in each polygon pattern. Experimental results show that a transformed routing pattern obtained by the proposed algorithm is good for existent CAD tools.