We introduce a novel variant of the well known d-dimensional bin (or vector) packing problem. Given a sequence of non-negative d-dimensional vectors, the goal is to pack these into as few bins as possible, of the smal...
详细信息
We introduce a novel variant of the well known d-dimensional bin (or vector) packing problem. Given a sequence of non-negative d-dimensional vectors, the goal is to pack these into as few bins as possible, of the smallest possible size. In the classical problem, the bin size vector is given and the sequence can be partitioned arbitrarily. We study a variation where the vectors have to be packed in the order in which they arrive, and the bin size vector can be chosen once in the beginning. This setting gives rise to two combinatorial problems: one in which we want to minimize the number of bins used for a given total bin size, and one in which we want to minimize the total bin size for a given number of bins. We prove that both problems are NP-hard, and propose an LP based bicriteria (1/epsilon, 1/1-epsilon)-approximation algorithm. We give a 2-approximation algorithm for the version F. T with a bounded number of bins. Furthermore, we investigate properties of natural greedy algorithms. and present an easy to implement heuristic, which is fast and performs well in practice. Experiments with the heuristic and an ILP formulation yield promising results on real world data. (C) 2008 Elsevier B.V. All rights reserved.
In contrast to conventional preprocessing aided spatial modulation (PSM), which carries partial information using the indexes of receive antennas, we exploit one receive antenna to implicitly convey information and me...
详细信息
In contrast to conventional preprocessing aided spatial modulation (PSM), which carries partial information using the indexes of receive antennas, we exploit one receive antenna to implicitly convey information and meanwhile harvest energy at the remaining antennas. Based on this, we propose two novel beamforming schemes. The first scheme is to maximize the sum energy harvested by the receiver. And the second scheme is to maximize the minimum receiving power on each antenna except for the antenna that conveys information. A closed form solution and an iterative algorithm are given, respectively. Simulation results demonstrate that proposed two schemes can harvest a certain amount of energy with nearly same achievable rate compared to the benchmark schemes. But the second scheme is superior to the first scheme and PSM scheme in terms of bit error rate (BER) performance.
Recently, energy dissipation for computations on FPGAs has become an important performance metric. In this paper, we summarize our recent efforts in developing an algorithm-level design methodology for optimizing the ...
详细信息
Recently, energy dissipation for computations on FPGAs has become an important performance metric. In this paper, we summarize our recent efforts in developing an algorithm-level design methodology for optimizing the energy performance of FPGA based implementations. For kernels, our design methodology consists of four steps: domain selection, domain-specific energy modeling, domain-space exploration and low-level simulation. To achieve system-level energy-efficiency, we outline a design methodology that integrates the kernel-level design methodology. Both the design methodologies can be used to achieve not only energy-efficiency but also latency, area, and power efficiency. We consider signal processing kernels as illustrative examples and demonstrate energy and time efficient algorithms and implementations for these on FPGAs. Example energy performance optimization through algorithmic optimizations include the 29-51% improvement in energy performance for a matrix multiplication kernel, 57-78% improvement for a FFT kernel and the 10-60% improvement for a floating-point LU decomposition kernel over state-of-the-art implementations. Similarly, an improvement of 41 to 46% in energy performance was achieved by the system-level design approach over a greedy approach for a MVDR adaptive beamforming application. Finally we briefly describe a high-level tool for obtaining parameterized and energy-efficient designs on FPGAs.
An optimal algorithm for layout of CMOS functional cells, in the gate-matrix style, is proposed. A novel simultaneous graph partitioning technique, which facilitates concurrent partitioning of the p-part and n-part of...
详细信息
An optimal algorithm for layout of CMOS functional cells, in the gate-matrix style, is proposed. A novel simultaneous graph partitioning technique, which facilitates concurrent partitioning of the p-part and n-part of a CMOS cell, is introduced. The proposed algorithm lays out a given cell with n gates in O(log n ) rows, and runs in O( n log n ) time. Optimality of this bound is established by proving that there are instances of the problem that require ω (log n ) rows. The algorithm has been implemented and experimental results are included.
The dense granular flow spallation target is a new target concept chosen for the Accelerator-Driven Subcritical (ADS) project in China. For the R&D of this kind of target concept, a dedicated Monte Carlo (MC) prog...
详细信息
The dense granular flow spallation target is a new target concept chosen for the Accelerator-Driven Subcritical (ADS) project in China. For the R&D of this kind of target concept, a dedicated Monte Carlo (MC) program named GMT was developed to perform the simulation study of the beam-target interaction. Owing to the complexities of the target geometry, the computational cost of the MC simulation of particle tracks is highly expensive. Thus, improvement of computational efficiency will be essential for the detailed MC simulation studies of the dense granular target. Here we present the special design of the GMT program and its high efficiency performance. In addition, the speedup potential of the GPU-accelerated spallation models is discussed. (C) 2017 Elsevier B.V. All rights reserved.
Information-centric networking (ICN) is a popular research topic. At its heart is the concept of in-network caching. Various algorithms have been proposed for optimizing ICN caching, many of which rely on collaborativ...
详细信息
Information-centric networking (ICN) is a popular research topic. At its heart is the concept of in-network caching. Various algorithms have been proposed for optimizing ICN caching, many of which rely on collaborative principles, i.e. multiple caches interacting to decide what to store. Past work has assumed altruistic nodes that will sacrifice their own performance for the global optimum. We argue that this assumption is insufficient and oversimplifies the reality. We address this problem by modeling the in-network caching problem as a Nash bargaining game. We develop optimal and heuristic caching solutions that consider both performance and fairness. We argue that only algorithms that are fair to all parties involved in caching will encourage engagement and cooperation. Through extensive simulations, we show our heuristic solution, FairCache, ensures that all collaborative caches achieve performance gains without undermining the performance of others.
In this paper, we show the first comprehensive experimental study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance...
详细信息
In this paper, we show the first comprehensive experimental study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance, we build a model to depict how various parameters affect the reading performance. Through our model, we have designed very efficient algorithms to maximize the time-efficiency and energy-efficiency by adjusting the reader's power and moving speed. Our experiments show that our algorithms can reduce the total scanning time by 50 percent and the total energy consumption by 83 percent compared to the prior solutions.
Estimation of a binary source using multiple observers, a variant of the so called Chief Executive Officer (CEO) problem, is considered. A low-complexity Distributed Joint Source Channel Coding (D-JSCC) based on the P...
详细信息
Estimation of a binary source using multiple observers, a variant of the so called Chief Executive Officer (CEO) problem, is considered. A low-complexity Distributed Joint Source Channel Coding (D-JSCC) based on the Parallel Concatenated Convolutional Codes (PCCC) is implemented in a cluster of sensors in a distributed fashion. Convergence of the iterative decoder is analyzed by utilizing EXtrinsic Information Transfer (EXIT) chart technique to determine the convergence region in terms of the sensors observation accuracy and channel SNR, where the iterative decoder outperforms the non-iterative one. This leads to design of a bi-modal decoder that adaptively switches between the iterative and non-iterative modes in order to avoid inefficient iterative information exchange without compromising the resulting Bit Error Rate (BER). This adaptive decoding algorithm saves the computational power and decoding time by a factor of about 10 by avoiding unnecessary iterations.
The specialty of the patterns is that they are present in many disciplines, even our world is organized by them. The application of a regular structure in the field of product design may also open new possibilities. A...
详细信息
The specialty of the patterns is that they are present in many disciplines, even our world is organized by them. The application of a regular structure in the field of product design may also open new possibilities. An automatized pattern can be used in many industries, such as interior design, paper industry, and so on. In this article we can see an example for utilization in electronic industry. The innovation is the pattern applied to the product, which was created with a new mathematical method. The goal was to develop a fully automatized general method. The description of the Generalized design Pattern Vector (GDPV) which contains the functions of geometric transformations is also included.
In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-...
详细信息
In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.
暂无评论