In order to build a fault-tolerant network, heterogeneous facilities are arranged in the network to prevent homogeneous faults from causing serious damage. This paper uses edge-colored graph to investigate the feature...
详细信息
In order to build a fault-tolerant network, heterogeneous facilities are arranged in the network to prevent homogeneous faults from causing serious damage. This paper uses edge-colored graph to investigate the features of a network topology which is survivable after a set of homogeneous devices malfunction. We propose an approach to designing such networks under arbitrary parameters. We also show that the proposed approach can be used to optimize inter-router connections in network-on-chip to reduce the additional consum!otion of energy and time delay.
The target coverage is an important yet challenging problem in wireless sensor networks, especially when both coverage and energy constraints should be taken into account. Due to its nonlinear nature, previous studies...
详细信息
The target coverage is an important yet challenging problem in wireless sensor networks, especially when both coverage and energy constraints should be taken into account. Due to its nonlinear nature, previous studies of this problem have mainly focused on heuristic algorithms; the theoretical bound remains unknown. Moreover, the most popular method used in the previous literature, i.e., discretization of continuous time, has yet to be justified. This paper fills in these gaps with two theoretical results. The first one is a formal justification for the method. We use a simple example to illustrate the procedure of transforming a solution in time domain into a corresponding solution in the pattern domain with the same network lifetime and obtain two key observations. After that, we formally prove these two observations and use them as the basis to justify the method. The second result is an algorithm that can guarantee the network lifetime to be at least (1 - ε) of the optimal network lifetime, where ε can be made arbitrarily small depending on the required precision. The algorithm is based on the column generation (CG) theory, which decomposes the original problem into two sub-problems and iteratively solves them in a way that approaches the optimal solution. Moreover, we developed several constructive approaches to further optimize the algorithm. Numerical results verify the efficiency of our CG-based algorithm.
Equipped with 512-bit wide SIMD inst d large numbers of computing cores, the emerging x86-based Intel(R) Many Integrated Core (MIC) architecture ot only high floating-point performance, but also substantial ...
详细信息
Equipped with 512-bit wide SIMD inst d large numbers of computing cores, the emerging x86-based Intel(R) Many Integrated Core (MIC) architecture ot only high floating-point performance, but also substantial off-chip memory bandwidth. The 3D FFT (three-di fast Fourier transform) is a widely-studied algorithm; however, the conventional algorithm needs to traverse the three times. In each pass, it computes multiple 1D FFTs along one of three dimensions, giving rise to plenty of rided memory accesses. In this paper, we propose a two-pass 3D FFT algorithm, which mainly aims to reduce of explicit data transfer between the memory and the on-chip cache. The main idea is to split one dimension into ensions, and then combine the transform along each sub-dimension with one of the rest dimensions respectively erence in amount of TLB misses resulting from decomposition along different dimensions is analyzed in detail. el parallelism is leveraged on the many-core system for a high degree of parallelism and better data reuse of loc On top of this, a number of optimization techniques, such as memory padding, loop transformation and vectoriz employed in our implementation to further enhance the performance. We evaluate the algorithm on the Intel(R) PhiTM coprocessor 7110P, and achieve a maximum performance of 136 Gflops with 240 threads in offload mode, which ts the vendor-specific Intel(R)MKL library by a factor of up to 2.22X.
In this paper, we present a hybrid circular queue method that can significantly boost the performance of stencil computations on GPU by carefully balancing usage of registers and shared-memory. Unlike earlier methods ...
详细信息
In this paper, we present a hybrid circular queue method that can significantly boost the performance of stencil computations on GPU by carefully balancing usage of registers and shared-memory. Unlike earlier methods that rely on circular queues predominantly implemented using indirectly addressable shared memory, our hybrid method exploits a new reuse pattern spanning across the multiple time steps in stencil computations so that circular queues can be implemented by both shared memory and registers effectively in a balanced manner. We describe a framework that automatically finds the best placement of data in registers and shared memory in order to maximize the performance of stencil computations. Validation using four different types of stencils on three different GPU platforms shows that our hybrid method achieves speedups up to 2.93X over methods that use circular queues implemented with shared-memory only.
Network virtualization is a promising approach for resource management that allows customized Virtual Networks (VNs) to be multiplexed on a shared physical infrastructure. A key function that network virtualization ...
详细信息
Network virtualization is a promising approach for resource management that allows customized Virtual Networks (VNs) to be multiplexed on a shared physical infrastructure. A key function that network virtualization can provide is Virtual Network Embedding (VNE), which maps virtual networks requested by users to a shared substrate network maintained by an Internet service provider. Existing research has worked on this, but has primarily focused on maximizing the revenue of the Internet service provider. In this paper, we consider energy-aware virtual network embedding, which aims at minimizing the energy consumption for embedding virtual networks in a substrate network. In our optimization model, we consider energy consumption of both links and nodes. We propose an efficient heuristic to assign virtual nodes to appropriate substrate nodes based on priority, where existing activated nodes have higher priority for hosting newly arrived virtual nodes. In addition, our proposed algorithm can take advantage of activated links for embedding virtual links so as to minimize total energy consumption. The simulation results show that, for all the cases considered, our algorithm can improve upon previous work by an average of 12.6% on acceptance rate, while the consumed energy can be reduced by 12.34% on average.
We extend static filtering in [8], a query optimization strategy based on seminaive evaluation on system graphs, so that it can efficiently handle stratified programs without extra overhead. The computation of static ...
详细信息
We extend static filtering in [8], a query optimization strategy based on seminaive evaluation on system graphs, so that it can efficiently handle stratified programs without extra overhead. The computation of static filters is formalized as a transformation so that the least fixed point of the transformation can be the static filters. The static filtering on stratified programs is shown to be complete with respect to the iterated fixed point semantics.
A syntactic error repair model is proposed, and is defined as a partial function from strings to sentences. The replacement of a substring of a string with a substring of a sentence is described by a repair pattern, w...
详细信息
A syntactic error repair model is proposed, and is defined as a partial function from strings to sentences. The replacement of a substring of a string with a substring of a sentence is described by a repair pattern, which is roughly a pair of strings of grammar symbols. The model can be efficient with some restriction on repair patterns. An LR-based implementation of the model is discussed.
The left context in LR-based parsing is the sequence of states in the parsing stack. The right context is the vocabulary strings to appear for a given left context. We propose an efficient method of computing right co...
详细信息
The left context in LR-based parsing is the sequence of states in the parsing stack. The right context is the vocabulary strings to appear for a given left context. We propose an efficient method of computing right context for LR-based syntax error repair. The efficiency of our method is achieved from removing some redundancies in the method of previous work.
作者:
KIM, DHCHOE, KMProgramming Languages Laboratory
Department of Computer Science Korea Advanced Institute of Science and Technology 371-1 Kusong-Dong Yusang-Gu Taejon 305-701 South Korea
An efficient backward execution algorithm in the AND/OR Process Model for parallel evaluation of logic programs is proposed. The efficiency of the algorithm is achieved by means of information acquired during executio...
详细信息
An efficient backward execution algorithm in the AND/OR Process Model for parallel evaluation of logic programs is proposed. The efficiency of the algorithm is achieved by means of information acquired during execution of clauses. The algorithm is considered to be efficient in the sense that it issues fewer number of cancel messages and avoids unnecessary resetting operations. Furthermore, it performs independent redoing and resetting more concurrently than other related works.
Floor plans can provide valuable prior information that helps enhance the accuracy of indoor positioning systems. However, existing research typically faces challenges in efficiently leveraging floor plan information ...
详细信息
暂无评论