The rapid increases in model parameter sizes introduces new challenges in pre-trained model loading. Currently, machine learning code often deserializes each parameter as a tensor object in host memory before copying it to device memory. We found that this approach underutilized storage throughput and significantly slowed down loading large models with a widely-used model file formats, safetensors. In this work, we present fastsafetensors, a Python library designed to optimize the deserialization of tensors in safetensors files. Our approach first copies groups of on-disk parameters to device memory, where they are directly instantiated as tensor objects. This design enables further optimization in low-level I/O and high-level tensor preprocessing, including parallelized copying, peer-to-peer DMA, and GPU offloading. Experimental results show performance improvements of 4.8x to 7.5x in loading models such as Llama (7, 13, and 70 billion parameters), Falcon (40 billion parameters), and the Bloom (176 billion parameters).

Determining the root cause of performance regression for microservices is challenging. The topological cascading performance implications among microservices hide the source of the problem. Additionally, the lack of knowledge about application phases can potentially lead to false-positive critical service detection. Service resource utilization is an imperfect proxy for application performance, potentially leading to false positives. Therefore, in this work, we propose a new performance testing framework that leverages hidden Berkeley Packet Filter (BPF) kernel metrics to locate root causes of performance regression. The framework applies a systematic multi-level approach to analyze microservice performance without intrusive code instrumentation. First, the framework constructs an attributed graph with microservice requests, scores the services to identify the critical paths, and ranks the low-level metrics to highlight the root cause of performance regression. Through judiciously designed experiments, we evaluated the metric collection overhead, showing less than 18% more latency when the application is running across hosts and 9% within the same host. In addition, depending on the application, no overhead is experienced, while the state-of-the-art approach presented up to 1060% more latency. The microservice benchmark evaluation shows that MicroLens can successfully identify the set of root causes and that the causes vary when the application is running in different infrastructures.

Containerization and application variety bring many challenges in automating evaluations for performance tuning and comparison among infrastructure choices. Due to the tightly-coupled design of benchmarks and evaluation tools, the present automated tools on Kubernetes are limited to trivial microbenchmarks and cannot be extended to complex cloudnative architectures such as microservices and serverless, which are usually managed by customized operators for setting up workload dependencies. In this paper, we propose AutoDECK, a performance evaluation framework with a fully declarative manner. The proposed framework automates configuring, deploying, evaluating, summarizing, and visualizing the benchmarking workload. It seamlessly integrates mature Kubernetes-native systems and extends multiple functionalities such as tracking the image-build pipeline, and auto-tuning. We present five use cases of evaluations and analysis through various kinds of bench-marks including microbenchmarks and HPC/AI benchmarks. The evaluation results can also differentiate characteristics such as resource usage behavior and parallelism effectiveness between different clusters. Furthermore, the results demonstrate the benefit of integrating an auto-tuning feature in the proposed framework, as shown by the 10% transferred memory bytes in the Sysbench benchmark.

Containerized applications have become widely used in modern software development due to their high flexibility and lightweight deployment. Currently, there exists a large set of publicly available container images with many different operating systems (OSs) and versions. As a result, developers typically select images carefully on the basis of memory footprint versus flexibility with available libraries. However, information regarding performance is insufficient. We have verified that different OS-based images with different versions vary the performance of certain applications running in them. Additionally, minor updates in container images, without changing its versions, also affect application performance. Therefore, to understand application performance, it is important to determine impact on performance in different container images along with the continuous monitoring of the minor changes. Since existing performance test frameworks do not encompass the required features to analyze performance regressions in container images, in this paper, we introduce ImageJockey, an original test framework to continuously evaluate the performance of a broad range of container images. Our framework enables experiments of container benchmarks with periodic image builds, simple container orchestration, metrics collection, and result visualization. We demonstrate the usefulness of our framework through case studies that analyze the performance characteristics of sixteen container images and nine popular benchmarks. The experimental results show that there is a noticeable performance variation due to the deployed environments and characteristics of Alpine and JDK images.

Achieving fast, scalable, and cost-effective genome analytics is always important to open up a new frontier in biomedical and life science. Genome Analysis Toolkit (GATK), an industry-standard genome analysis tool, improves its scalability and performance by leveraging Spark and HDFS. Spark with HDFS has been a leading analytics platform in a past few years, however, the system cannot exploit full advantage of cloud elasticity in a recent modern cloud. In this paper we investigate performance characteristics of GATK using Spark with HDFS and identify scalability issues. Based on a quantitative analysis, we introduce a new approach to utilize Cloud Object Storage (COS) in GATK instead of HDFS, which can help decoupling compute and storage. We demonstrate how this approach can contribute to the improvement of the entire pipeline performance and cost saving. As a result, we demonstrate GATK with IBM COS can achieve up to 28% faster than GATK with HDFS. We also show that this approach can achieve up to 67 % cost saving in total, which includes the time for data loading and whole pipeline analysis.

While Hadoop is the de facto standard big-data middleware, many frameworks have been developed on top of it. Since many SQL-on-Hadoop systems are available, we often consider which engine is best for our queries. We can choose not only query engines but also Java virtual machines (JVMs) as well. As their systems become more complex, however, it is not always true that a single system performs best at any time. Moreover, the performance of a mismatched system may degrade greatly. To exploit the best performance, it is important to know what type of queries are suitable for a system and then to schedule queries for the appropriate system. In this paper, we evaluated the TPC-DS benchmark on a combination of query engines (Spark and Tez) and JVMs (J9 and OpenJDK). We found that using different engines lead to a drawback of over 10 times and that using different JVMs leads to a drawback of 3 times. We also analyzed the characteristics of each combination and then proposed classification models for selecting the best combination of systems with a generated query plan. As a result, we achieved a performance improvement of up to two times in total with the classifier.

Columnar storage is a data source for data analytics in distributed computing frameworks. For portability and scalability, columnar storage is built on top of existing distributed file systems with columnar data representations such as Parquet, RCFile, and ORC. However, these representations fail to utilize high-level information (e.g., columnar formats) for low-level disk buffer management in operating systems. As a result, data analytics workloads suffer from redundant memory buffers with expensive garbage collections, unnecessary disk readahead, and cache pollution in the operating system buffer cache.We propose column cache, which unifies and re-structures the buffers and caches of multiple software layers from columnar storage to operating systems. Column cache leverages high-level information such as file formats and query plans for enabling adaptive disk reads and cache eviction policies. We have developed a column cache prototype for Apache Parquet and observed that our prototype reduced redundant resource utilization in Apache Spark. Specifically, with our prototype, Spark showed a maximum speedup of 1.28x in TPC-DS workloads while increasing Linux page cache size by 18%, reducing total disk reads by 43%, and reducing garbage collection time in a Java virtual machine by 76%.

Deep convolutional neural networks (CNN) have shown their good performances in many computer vision tasks. However, the high computational complexity of CNN involves a huge amount of data movements between the computational processor core and memory hierarchy which occupies the major of the power consumption. This paper presents Chain-NN, a novel energy-efficient 1D chain architecture for accelerating deep CNNs. Chain-NN consists of the dedicated dual-channel process engines (PE). In Chain-NN, convolutions are done by the 1D systolic primitives composed of a group of adjacent PEs. These systolic primitives, together with the proposed column-wise scan input pattern, can fully reuse input operand to reduce the memory bandwidth requirement for energy saving. Moreover, the 1D chain architecture allows the systolic primitives to be easily reconfigured according to specific CNN parameters with fewer design complexity. The synthesis and layout of Chain-NN is under TSMC 28nm process. It costs 3751k logic gates and 352KB on-chip memory. The results show a 576-PE Chain-NN can be scaled up to 700MHz. This achieves a peak throughput of 806.4GOPS with 567.5mW and is able to accelerate the five convolutional layers in AlexNet at a frame rate of 326.2fps. 1421.0GOPS/W power efficiency is at least 2.5 to 4.1x times better than the state-of-the-art works.

The state-of-the-art customized accelerators of convolution neural networks (CNN) have achieved high throughput while the huge amount of data movements still remains as the dominant part of the total energy costs. In this paper, we propose an energy-efficient scheduling approach to find an efficient dataflow that minimizes data movements with limited hardware resource budgets. In detail, two-level nested loop transformations are proposed to separate memory and computing resource constraints. This allows us to fully exploit the potential of available memory resources for reducing off-chip memory traffic. Further, the proposed cross-loop model is capable of figuring out the data locality across nested loops in CNN algorithms. Finally, energy-delay production is employed as the evaluation criteria to balancing energy and throughput performance. The experimental results show our cross-loop model can reduce the off-chip data movements by 11-21% and achieve the theoretical optimum. Therefore, the proposed scheduling method can increase the energy efficiency by at least 8.7 times.

This paper presents a measurement-domain intra prediction coding framework that is compatible with compressive sensing (CS) based image sensors. In this framework, we propose a low-complexity intra prediction algorithm that can be directly applied to the measurements captured by the image sensor. Moreover, we propose a structural random 0/1 measurement matrix, embedding the block boundary information that can be extracted from the measurements for intra prediction. Experiment results show that our proposed framework can compress the measurements and increase coding efficiency, with 30% BD-rate reduction compared to the direct output of CS based sensors. This can significantly save both the energy consumption and the bandwidth in communication of wireless camera systems to be massively deployed in the era of IoT.

The paper presents an algorithm to generate a series of deterministic ternary matrices, which are compatible with the new generation of CMOS image sensor (CIS), Compressed Sensing (CS) based CIS (CS-CIS). The proposed matrices are derived from the approximate DCT, hence preserving the energy compaction property as DCT does. With the proposed 2D-zigzag trimming, the limited measurements could compact most of the energy. The experiment result shows that our proposed matrix contributes a significant improvement in image quality and bitrate saving of 5.7 dB BD-PSNR increase on average comparing with the random binary matrix used in the-state-of-art CS-CIS.

In this paper, we focus on the low-power scheduling problem with multiple threshold and/or supply voltage technologies in high-level synthesis. We propose a unified scheduling approach which is applicable to various optimization problems, including: 1) dynamic power and resource usage co-optimization; 2) leakage power optimization; and 3) dynamic power and leakage power co-optimization. To deal with different objectives with high flexibility, three problems are divided into two common subproblems including delay assignment and resource density variance minimization, then a vertex potential-based mobility allocation model is proposed to solve two subproblems simultaneously. Experimental results show that, for dynamic power and resource co-optimization, our scheduling approach produces optimum solutions for all six benchmarks with 15 groups of data; for leakage power optimization it also greatly excels the latest existing work, by 20% leakage power reduction and 52 times speedup. Besides, for dynamic and leakage power co-optimization, the Pareto solutions are studied.

Ultrahigh definition television is becoming increasingly attractive and practical with the doubled compression performance delivered by High Efficiency Video Coding (H.265/HEVC). Meanwhile, implementation of real-time video codecs is challenged by not only the huge throughput and memory bandwidth requirements but also the increased complexity of new algorithms. For motion compensation (MC) that is a known bottleneck in video decoding, the enlarged and diversified prediction unit sizes impose notably higher difficulties in trading off area, power, and memory traffic. This paper presents a very large scale integration implementation of HEVC MC that supports 7680 × 4320@60 frames/s bidirectional prediction. The MC design incorporates a highly efficient cache realized by novel architecture optimizations including distance biased directing mapping, eight-bank memory structure, row-based miss information compression, and mask-based block conflict checking. As a result, the proposed design not only achieves 8× throughput enhancement but also improves hardware efficiency by at least 2.01 times, in comparison with prior arts.

Data path interconnection on VLSI chips usually consumes a significant amount of both power and area. In this paper, we focus on the port assignment problem for binary commutative operators for interconnection complexity reduction. First, the port assignment problem is formulated on a constraint graph, and a practical method is proposed to find a valid and initial solution. For solution optimization, an elementary spanning-tree-transformation-based local search algorithm is proposed. To improve the efficiency of optimization, a matrix formulation, which meets the simplex tabuleau format, is proposed and thus the simplex method is adopted for optimization. Moreover, operation pivoting and successive pivoting are discussed for algorithm speedup. The experimental results show that on the randomly generated test cases, the matrix-based algorithm shows the highest solution optimality and is five times faster than the elementary transformation method. On the real high-level synthesis benchmarks, the matrix-based method reduced 14% interconnections, while the previous greedy algorithm reduced 8% on average.

Sample adaptive offset (SAO) is a newly introduced in-loop filtering component in H.265/High Efficiency Video Coding (HEVC). While SAO contributes to a notable coding efficiency improvement, the estimation of SAO parameters dominates the complexity of in-loop filtering in HEVC encoding. This paper presents an efficient VLSI design for SAO estimation. Our design features a dual-clock architecture that processes statistics collection (SC) and parameter decision (PD), the two main functional blocks of SAO estimation, at high- and low-speed clocks, respectively. Such a strategy reduces the overall area by 56% by addressing the heterogeneous data flows of SC and PD. To further improve the area and power efficiency, algorithm-architecture co-optimizations are applied, including a coarse range selection (CRS) and an accumulator bit width reduction (ABR). CRS shrinks the range of fine processed bands for the band offset estimation. ABR further reduces the area by narrowing the accumulators of SC. They together achieve another 25% area reduction. The proposed VLSI design is capable of processing 8k at 120-frames/s encoding. It occupies 51k logic gates, only one-third of the circuit area of the state-of-the-art implementations.

The exponential increase in leakage power and the substantial power-saving opportunities provided by scheduling have made dual-threshold voltage (dual-Vth) an attractive choice for low-leakage-power designs. In this paper, we work under the assumption that functional units (FUs) are allocated after scheduling, and fully explore the solution space of scheduling with dual-Vthoperations to optimize the leakage power of the FUs. First, a binding conflict graph (BCG)-based scheduling method is presented to minimize the number of FUs. Second, the BCG-based method is extended to allow scheduling with dual-Vthoperation targeting the minimization of leakage power. In timing-constrained scheduling, each operation in the data flow is initialized with low-Vth. Then, starting from an operation schedule with the timing constraint satisfied, we scale the sets of low-Vthoperations in the off-critical paths with high-Vthso as to reduce the number of low-VthFUs without increasing the total delay. Finally, a scheduling method for minimizing the leakage power under both timing and resource constraints is presented. The results of benchmark tests show that the proposed algorithms can reduce the leakage power reported in previous works by 10.2% while maintaining high circuit performance.

In this paper, we propose a data forwarding method for efficient data gathering in wireless sensor networks with multiple mobile sinks which freely move in the target region. In our proposed method, each sensor node forwards data packets based on information on connectivity (the status of connection with mobile sinks). As the way to share information on connectivity among neighboring nodes, we integrate push-based and pull-based mechanisms we have proposed in [5]. The integrated mechanism utilizes advertisement from the nodes with good connectivity together with request from the nodes which hold data to transmit. By the complementary use of these mechanisms, our proposed method reduces the traffic for sharing information while realizing an efficient data forwarding.

Enhancing source code quality of operating systems (OSes) is an essential and endless task in communities of commodity OSes. Unfortunately, improving the quality of the kernel code is not trivial because the kernel is large and complex. In particular, asynchronous events from peripheral devices such as interrupts make the improvement quite hard due to their low reproducibility. This paper presents Foxy Feed, a mechanism based on virtual machine monitors that helps to fix bugs caused by asynchronous device-level events. Foxy Feed forges device-level events and injects them to a debuggee kernel at the timing specified in advance, and allows us to control the timing at which asynchronous events occur for the debugging purpose. Using our prototype implementation of Foxy Feed, which is based on Xen 4.1.0, we demonstrate that Foxy Feed reproduces failures caused by device-triggered bugs in Linux and gives significant clues to the root causes.

In this work, we focus on the problem of latency-constrained scheduling with consideration of multiple voltage technologies in High-level synthesis. Without the resource concern, we propose an Integer Linear Programming (ILP) formulation and further relax it to a piecewise Linear Programming (LP) problem, which is optimally solved using the efficient piecewise-linear extended network simplex method(PLNSM). The experimental results showed 80X+ speedup compared to the general LP formulation. Considering the resource usage, we propose a two-stage heuristic Network Simplex Method based Power-efficient Multiple Voltage Scheduling(NPMVS) method. Firstly, the above relaxed LP formulation is modified to perform mobility allocation and delay assignment for the operations so as to minimize the power and the differences between the allocated operation mobilities and the predefined target mobilities. The modified formulation is solved using the PLNSM and iteratively performed to minimize power and resource density variation in control steps by gradually updating the predefined target mobilities. Secondly, with the allocated operation mobilities, we apply dependency-free operation scheduling with the objective of minimizing the resource usage. Experimental results show that the proposed method can produce optimum solutions for all 6 benchmarks with 14 groups of data in a maximum time of 0.25 second.

As technology scaling, three-dimensional integrated circuits (3D-ICs) are emerging as a promising solution to address the challenges in system on chips (SoCs). Moreover, it's a necessity to design an efficient Network-on-Chip (NoC) topology for the interconnection issues of 3D SoCs. In this paper, we propose a topology-aware floorplanning method to determine the power-performance efficient 3D NoC topology. Unlike the previous works which explore the path allocation of the NoC components and Through-Silicon Vias (TSVs) assignment after the floorplan of cores is fixed, we integrate these steps (the clustering of cores + the placement of cores and switches + the path allocation + the TSV-aware topology evaluation) within the 3D floorplanning procedure. Experimental results show the effectiveness of our method.

In this paper, we address the problem of scheduling operations into control steps with dual threshold voltage (dual-Vth) technique under timing and resource constraints. Recently, some scheduling methods are proposed based on the mobility overlap removal, and it is a hard problem to remove the mobility overlap optimally. There might be no feasible solution with an improper mobility overlap removal. In this work, we implement the mobility overlap removal together with dual threshold voltage technique to minimize the total leakage power. A simulated-annealing based method is introduced to explore the optimal solution. For each mobility overlap removal, a probability-based method is proposed to schedule operations at appropriate control steps, and to assign them with proper threshold voltages. The experimental results show the effectiveness of the proposed method.

In this paper, we propose a method of floorplanning with voltage island generation for system-on-chips (SoC) designs, which is deeply coupled with voltage island partitioning and voltage assignment, and has a good scalability. Floorplans with voltage islands are represented using nested Sequence Pairs, where the cores involved in the same voltage island consecutively appear in the sequences. Starting from a randomly generated initial floorplan, where each non chip-level core occupies an individual voltage island, we iteratively improve the solution by removing a core from the floorplan, then, inserting back the core by trying all the possible O(n2) block positions, which are defined as the combinations of insertion points and voltage islands. An almost linear algorithm is devised to roughly but quickly filter many worse block positions, in each iteration, considering fixed-outline constraints, wirelength, power, power/ground routing resources, and level shifters. Compared with the latest work, the proposed method shows 9.74% and 21.04% improvements respectively on the wirelength and power when all the blocks are hard. When soft blocks are involved, the proposed method shows 12.38% wirelength reduction and 3.10% more power saving with a penalty of 7.5% whitespace. Moreover, more than 20X speedups can be obtained for the large test cases.

In this paper, we propose a novel mapping method for FPGA with dual-output LUT based logic elements (LEs), aiming for power reduction. Recently, a new kind of LE-Adaptive Logic Module (ALM), which contains a dual-output fracturable LUT instead of traditional single-output K-LUT, is used in Altera's high-end FPGA products to obtain a good trade-off between area and delay. To map a design to ALMs, we introduce a LUT-merging step after K-LUT technology mapping, where the LUTs are merged into ALMs. We propose a max-weight matching based method for the LUT-merging, trying to reduce the number of used ALMs and meanwhile reduce power consumption. Experimental results show that, compared with a previous LUT-merging method for area-optimization, though resulting in a little more ALMs, our low power LUT-merging method improves the power by 7.48%.

This paper shows that the use of Weighted Finite-State Transducer (WFST) significantly eliminates large-scale ambiguity in scene text recognition, especially for Japanese Kanji characters. The proposed method consists of two WFSTs called WFST-OCR and WFST-Lexicon. WFST-OCR handles the multiple hypotheses caused by erroneous text location, character segmentation and character recognition processes. The following WFST-Lexicon and its convolution of WFST-OCR resolve the hypotheses. The WFSTs integrate the conventional OCR and post-processing processes into one process. The benefit from the proposed method is that all the ambiguities are held as WFST data, and solved in one integrated step, the system outputs texts that are statistically consistent with regard to segmentation possibilities and the given language model. An experimental system demonstrates practical performance in spite of the hypothesis complexity inherent in the ICDAR test set and Kanji character texts.

As technology advances, 3-D stacking of silicon layers is emerging as a promising approach to address the integration challenges faced by current System-on-Chips (SoCs). Designing efficient Network- on-Chips (NoCs) is necessary to handle the 3-D interconnect complexity. In this paper, we present a four-stage synthesis approach to determine the power-performance efficient 3-D NoC topology for the application. First, we propose an algorithm to explore optimal clustering of cores during 3-D floorplanning. Then, an Integer Linear Programming (ILP) algorithm is proposed to place switches and network interfaces on the 3-D floorplan. Thirdly, a power and timing aware path allocation algorithm is carried out to determine the connectivity across different switches. Last, a min-cost max-flow based algorithm is proposed for Through-Silicon Via (TSV) assignment to minimize the link power consumption. Experimental results show the effectiveness of the proposed algorithm.

As technology advances, 3-D ICs can significantly alleviate the interconnect problem coming with the decreasing of feature size and are promising for heterogeneous integration. In 3-D ICs, one of the key challenges is the vertical technology, using through-silicon via (TSV) for different device layers connection. In this paper, by noticing the TSV assignment comes under the influence of the whitespace distribution in a given 3-D floorplan, we proposed an algorithm called whitespace insertion (WSI) based on the floorplan-representation Sequence Pair to make the whitespace distribution in the given floorplan more reasonable for TSV insertion. When given 3-D circuit placement or floorplan results, we also proposed a minimum spanning tree based algorithm for TSV assignment to minimize the total wire length, assuming each net may have at most one TSV on each device layer. Experimental results show that, in the given 3-D floorplans there is a huge gap about 45.54% of the wire length increase between the ideal and the practice. And based on our method, the total wire length can be reduced by 13% on average without changing the chip area.

In modern sub-micron design, achieving low-skew clock distributions is facing challenges for high-performance circuits. Symmetric global clock distribution and clock tree synthesis (CTS) for local clock optimization are used so far, but new methodologies are necessary as the technology node advances. In this paper, we study the register placement problem which is a key component of local clock optimization for highperformance circuit design along with local clock distribution. We formulate it as a minimum weighted maximum independent set problem on a weighted conflict graph and propose a novel efficient two-stage heuristic to solve it. To reduce the graph size, techniques based on register flipping and Manhattan circle are also presented. Experiments show that our heuristic can place all registers without overlaps and achieve significant improvement on the total and maximal register movement.

In this paper, we propose a fixed-outline floorplanning (FOFP) method [insertion-after-remove (IAR) FP]. An elaborated method for perturbing solutions, the IAR, is devised. This perturbation uses a technique of enumerating block positions, which is implemented based on the floorplan-representation sequence pair. The proposed perturbation method can greatly accelerate searching-based algorithms, such as simulated annealing, by skipping many solutions that fail to meet the fixed-outline constraint. Moreover, based on the analysis of the diverse objective functions used in the existing research works, we suggest for the FOFP a new objective function which is still effective when combined with other objectives. Experimental results show that, if area and wirelength are optimized simultaneously, using less time, the proposed method obtains much higher average success rate for the FOFP with various aspect ratios, while the wirelength with the fixed-outline constraint is reduced by 20% on average, compared with the latest fixed-outline floorplanners. On the other hand, we validated once more by experiments that an aspect ratio close to one is beneficial to wirelength, and hence, a larger area weight is necessary for the FOFP with a larger aspect ratio to ensure feasible solutions.

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 isin G (u ne v), (G satisfies |{uv}| + |{vu}|) = {( (r11if u, v isin A) (r12if u isin A, v isin B) (r22if u, v isin B)), where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r11, r12, r22)-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 (Takahashi et al., 2006). In this paper, we propose an algorithm for constructing a "tournament" from such a score sequence pair.

In this paper, we propose a stable fixed-outline floorplanning method(IARFP). An elaborated method for perturbing solutions, Insertion after Remove(IAR), is devised for the simulated annealing. The IAR operation uses the technique of enumerating positions in Sequence Pair and greatly accelerates the searching. Moreover, based on the analysis of diverse objective functions used in the existing researches, we suggest a new objective function, which is still effective when combined with other objectives, for the fixed-outline floorplanning. Compared with the previous fixed-outline floorplanners, the proposed method is effective and efficient. Experiments showed that the proposed fixed-outline floorplanner achieved 100% success rate efficiently when optimizing area and wire-length simultaneously, while getting much smaller wirelength. On the other hand, we validated once more by experiments that aspect ratio close to one is beneficial to wire-length.

This paper reviews practical video delivery technologies, examining existing mobile networks, commercialized or standardized transport, and coding technologies. Compression efficiency, power dissipation, and error control are intrinsic issues in wireless video delivery. Among these issues, error control technologies are evaluated at four layers: 1) layer-1/2 transport; 2) end-to-end transport layer such as TCP/IP or RTP/UDP/IP; 3) error-resilience tool and network adaptation layer) and 4) source coder layer. Layer-1/2 transport tends to provide two distinct conditions: one quasi-error-free, in which upper layer error control technologies show a limited improvement, and one with a burst of errors during the fading period, in which the adaptability of error control is essential. Emerging mobile network quality of service will have a large variation of bandwidth and delay. Thus, adaptive rate control and error recovery are identified as more crucial issues for future research.

Feedback adaptation has been the basis for many media streaming schemes, whereby the media being sent is adapted in real time according to feedback information about the observed network state and application state. Central to the success of such adaptive schemes, the feedback must: 1) arrive in a timely manner and 2) carry enough information to effect useful adaptation. In this paper, we examine the use of feedback adaptation for media streaming in 3G wireless networks, where the media servers are located in wired networks while the clients are wireless. We argue that end-to-end feedback adaptation using only information provided by 3G standards is neither timely nor contain enough information for media adaptation at the server. We first show how the introduction of a streaming agent (SA) at the junction of the wired and wireless network can be used to provide useful information in a timely manner for media adaptation. We then show how optimization algorithms can be designed to take advantage of SA feedbacks to improve performance. The improvement of SA feedbacks in peak signal-to-noise ratio is significant over nonagent-based systems.

This paper describes a new hardware/software co-verification method for System-On-a-Chip, based on the integration of a C/C++ simulator and an inexpensive FPGA emulator. Communication between the simulator and emulator occurs via a flexible interface based on shared communication registers. This method enables easy debugging, rich portability, and high verification speed, at a low cost. We describe the application of this environment to the verification of three different complex commercial SoCs, supporting concurrent hardware and embedded software development. In these projects, our verification methodology was used to perform complete system verification at 0.2-1.1 MHz, while supporting full graphical interface functions such as "waveform" or "signal dump" viewers, and debugging functions such as "step" or "break".

A network agent located at the junction of wired and wireless networks can provide additional feedback information to streaming media servers to supplement feedbacks from clients. Specifically, it has been shown that feedbacks from the network agent have lower latency, and they can be used in conjunction with client feedbacks to effect proper congestion control. In this work, we propose the double-feedback streaming agent (DFSA) which further allows the detection of discrepancies in the transmission constraints of the wired and wireless networks. By working together with the streaming server and client, DFSA reduces overall packet losses by exploiting the excess capacity Of the path with more capacity. We show how DFSA can be used to support three modes of operation tailored for different delay requirements of streaming applications. Simulation results under high wireless latency show significant improvement of media quality using DFSA over non-agent-based and earlier agent-based streaming systems.

We describe the design and implementation of a new transport layer protocol, MMSP (mobile multimedia streaming protocol), that supports bicasting in combination with FEC. MMSP duplicates the packets to be sent through the creation of redundant packets that are Reed-Solomon coded and sends them through two different paths to avoid data loss during handover. We call this mechanism end-to-end robust IP soft handover; it enables mobile terminals to move without any data loss and also improves error resiliency against wireless errors. Thus it is well suited to many common real-time multimedia applications for which retransmission is inappropriate. Our architecture requires no changes to the existing IP networks so it allows for easy deployment. Our performance experiments show that while FEC processing causes some slight delay, such delay is allowable. Bicasting with FEC can provide high quality MPEG-4 transport even under high bit error rates.

A network agent located at the junction of wired and wireless networks can provide additional feedback information to streaming servers to supplement feedback from clients. Specifically, it has been shown that feedbacks from the network agent have lower latency, and can be used in conjunction with client feedbacks to effect proper congestion control. In this work, we propose the double feedback streaming agent (DFSA) which further allows the detection of discrepancies in the transmission constraints of the wired and wireless networks. By working together with the streaming server and client, DFSA reduce overall packet losses by exploiting the excess capacity of the path with more capacity. We show how DFSA can be used to support three modes of operation tailored for different delay requirements of streaming applications. Simulation results show noticeable improvement of media quality using DFSA over existing streaming systems.

We propose a of control architecture for mobile multimedia streaming in which RTP monitoring agents report QoS information to media servers. The RTP monitoring agents lie midway between wired networks and radio links, monitor RTP packets sent from media servers to mobile terminals, and report quality information to media servers so that the servers can realize network-adaptive QoS control. By analyzing the information sent from the agents, the servers can distinguish quality degradation caused by network congestion from that caused by radio link errors, and can improve service quality by controlling the transmission rate and robustness against packet loss. Simulation results show our implemented QoS control schemes that use the feedbacks from the agent and control transmission rate and robustness provide better video quality than a simple rate control mechanism.

Feedback adaptation has been the basis for many media streaming schemes whereby the media being sent is adapted according to feedback information about the channel. Central to the success of such adaptive schemes, the feedback must (1) arrive in a timely manner, and (2) carry enough information to effect useful adaptation. We examine the use of feedback adaptation for media streaming in a 3G wireless network, where the media servers are located in wired networks while the clients are wireless. We argue that end-to-end feedback adaptation using only information provided by 3G standards is neither timely, nor contain enough information for media adaptation at the server. We then show how the introduction of an streaming agent (SA) at the junction of the wired and wireless network can be used to provide useful information in a timely manner for media adaptation.

In this paper, we present a mobile streaming media CDN (Content Delivery Network) architecture in which content segmentation, request routing, pre-fetch scheduling, and session handoff are controlled by SMIL (Synchronized Multimedia Integrated Language) modification. In this architecture, mobile clients simply follow modified SMIL files downloaded from a streaming portal server; these modifications enable multimedia content to be delivered to the mobile clients from the best surrogates in the CDN. The key components of this architecture are 1) content segmentation with SMIL modification, 2) on-demand rewriting of URLs in SMIL, 3) pre-fetch scheduling based on timing information derived from SMIL, 4) SMIL updates by SOAP (Simple Object Access Protocol) messaging for session handoffs due to clients mobility. We also introduce QoS control with a network called an RTP monitoring agent to enable appropriate control of media quality based on both network congestion and radio link conditions. The current status of our prototyping on a mobile QoS testbed MOBIQ is reported in this paper. We are currently designing the SOAP-based APIs (Application Programmable Interfaces) needed for the mobile streaming media CDN and building the CDN over the current testbed.

We present an ordered tree (O tree) structure to represent nonslicing floorplans. The O tree uses only n(2+[lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2/sup 2n-2//n/sup l.5/). This is very concise compared to a sequence pair representation that has O((n!)/sup 2/) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n/sup 2/(n/4e)/sup n/). The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2/sup 5n-3//n/sup 1.5/) combinations. Given an O tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.

Recently, a deterministic algorithm based on the O-tree repre-sentation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time. 1.

We present an ordered tree, O-tree, structure to represent non-slicing floorplans. The O-tree uses only n (2 + ⎡lg n⎤) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y direction. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n! 2 2n- 2 / n 1.5). This is very concise compared to a sequence pair representation which has O((n!) 2) combinations. The approximate ratio of sequence pair and Otree combinations is O(n 2 (n /4e) n). The complexity of O-tree is even smaller than a binary tree structure for slicing floorplan which has O(n! 2 5n-3 /n 1.5) combinations. Given an O-tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O-tree. Empirical results on MCNC benchmarks show promising performance with average 16 % improvement in wire length, and 1 % less in dead space over previous CPU-intensive cluster refinement method. 1.

Abstract|This paper presents a new logic partitioning method for optimizing large scale circuits.The proposed method partitions a given circuit into transitive fanindisjoint sub-circuits by matrix operations, so that various optimization methods can be applied to each partitioned sub-circuit instead of the whole circuit.Experimental results show that the proposed method achieves high-quality design comparable to the one optimized for the whole circuits, with much shorter time(1/20).Thus, the circuits with over 10,000 gates can be optimized by the proposed partitioning.

New placement and global routing algorithms are proposed for standard cell layouts. The placement algorithm, called the hierarchical clustering with min-cut exchange (HCME), is effective to avoid being trapped in local optimum solutions. The global routing algorithm does not route the nets one by one and therefore, the results are independent of the net order and channel order. In this algorithm, channel width is minimized under a cost function, in which the trade-off between the minimization of net lengths and the minimization of the number of tracks is considered. These algorithms are simple and highly efficient. This is confirmed by computational experiments.

The authors present a single-chip VLSI chrominance/luminance (Y/C) separator that is economically fabricated for NTSC TV signals at 13.5-MHz CCIR standard sampling rate. In order to realize compactness and low power dissipation, two FIR filter architectures and a multiplier structure are proposed. A silicon compiler, which uses these structures, also contributes to fast and error-free VLSI development. The Y/C separator chip has 10.4-mm*11.7-mm die size and attains about 860-MOPS operating speed.>

A scheduling/allocation and control synthesis algorithm is presented. The proposed algorithm can achieve good resource sharing and synthesize an efficient control sequence for nested conditional branches as well as for straight-line codes. The condition vector concept is introduced to allow mutual exclusion to be detected among operators, and is used to produce more efficient control sequences. The condition vector concept is concerned with the handling of nested condition branches and can be used for other scheduling methods. Results obtained from several experiments indicate that the proposed algorithms are efficient and effective.>

This paper presents a new design method for custom LSI layouts. This method is based on layout compaction with automatic jog (wiring bend) generation in the layout. A dense chip design can be realized by this technique. Experimental results show that the chip size designed by using the proposed layout method is only 1.2-1.4 times larger than that resulting from manual layouts. Therefore, this compaction-based custom LSI layout design method is very effective for achieving a minimal chip layout design.

In the layout design of LSI chips, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two-layer channel. Nets are routed with horizontal segments on one layer and vertical segments on the other. Connections between two layers are made through via holes. Two new algorithms are proposed. These algorithms merge nets instead of assigning horizontal tracks to individual nets. The algorithms were coded in Fortran and implemented on a VAX 11/780 computer. Experimental results are quite encouraging. Both programs generated optimal solutions in 6 out of 8 cases, using examples in previously published papers. The computation times of the algorithms for a typical channel (300 terminals, 70 nets) are 1.0 and 2.1 s, respectively.