3584727
Simple offset assignment in presence of subword data
Many embedded architectures support indirect addressing mode with autoincrement/autodecrement. By maximizing the use of this mode, generation of explicit instructions for performing address arithmetic can be avoided and thus reductions in code size and improvements in performance are achieved. Bartley [2] and Liao et al. [16] developed a method for finding a storage layout for program variables so that the use of autoincrement/autodecrement could be maximized. They introduced the Simple Offset Assignment (SOA) problem and solved it using a Path Cover (PC) formulation.We observe that many media and network processing applications make extensive use of subword data. Therefore, for such applications, by packing multiple subword variables into a single word, we can generate storage layouts that further reduce the cost of address arithmetic in two ways. First the need for address arithmetic is reduced as variables that are packed together share the same address. Second opportunities for using autoincrement andautodecrement instructions are increased as layouts are now possible which place a variable adjacent to more than two variables. This approach has become feasible because of the recent trend in embedded processor design which allows subword variables that are packed together to be accessed and manipulated without incurring performance penalty. We introduce the SubWord Offset Assignment (SWOA) problem and solve it using a Path Cover with Node Coalescing (PCwNC) formulation. Node coalescing corresponds to packing of multiple subword variables into a single word while path covering corresponds to placement of variables in adjacent memory locations to enable the use of autoincrement/autodecrement. We present three heuristics to solve the PCwNC problem. Experiments show that when the program is optimized for code size, the three proposed algorithms achieve 26%, 26.9% and 32% reduction in the number of static explicit address arithmetic instructions over Liao et al.'s algorithm. The algorithms also achieve 14.5%, 22.1%and 22.7% reduction in stack frame size. If the program is optimized for performance, the algorithms achieve 24.3%, 24.7% and 30.2% reduction in the dynamic instruction count of explicit address arithmetic instructions.
3580064
Bit section instruction set extension of ARM for embedded applications
Programs that manipulate data at subword level, i.e. bit sections within a word, are common place in the embedded domain. Examples of such applications include media processing as well as network processing codes. These applications spend significant amounts of time packing and unpacking narrow width data into memory words. The execution time and memory overhead of packing and unpacking operations can be greatly reduced by providing direct instruction set support for manipulating bit sections.In this paper we present the Bit Section eXtension (BSX) to the ARM instruction set. We selected the ARM processor for this research because it is one of the most popular embedded processor which is also being used as the basis of building many commercial network processing architectures. We present the design of BSX instructions and their encoding into the ARM instruction set. We have incorporated the implementation of BSX into the Simplescalar ARM simulator from Michigan. Results of experiments with programs from various benchmark suites show that by using BSX instructions the total number of instructions executed at runtime by many transformed functions are reduced by 4.26% to 27.27% and their code sizes are reduced by `1.27% to 21.05%.
3592974
Code Compaction of Matching Single-Entry Multiple-Exit Regions
With the proliferation of embedded devices and systems, there is renewed interest in the generation of compact binaries. Code compaction techniques identify code sequences that repeatedly appear in a program and replace them by a single copy of the recurring sequence. In existing techniques such sequences are typically restricted to single-entry single-exit regions in the control flow graph. We have observed that in many applications recurring code sequences form single-entry multipleexit (SEME) regions. In this paper we propose a generalized algorithm for code compaction that first decomposes a control flow graph into a hierarchy of SEME regions, computes signatures of SEME regions, and then uses the signatures to find pairs of matching SEME regions. Maximal sized matching SEME regions are found and transformed to achieve code compaction. Our transformation is able to compact matching SEME regions whose exits may lead to a combination of identical and differing targets. Our experiments show that this transformation can lead to substantial reduction in code size for many embedded applications.
12626074
Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks
Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.
5530667
On achieving optimized capacity utilization in application overlay networks with multiple competing sessions
In this paper, we examine the problem of large-volume data dissemination via overlay networks. A natural way to maximize the throughput of an overlay multicast session is to split the traffic and feed them into multiple trees. While in single-tree solutions, bandwidth of leaf nodes may remain largely under-utilized, multi-tree solutions increase the chances for a node to contribute its bandwidth by being a relaying node in at least one of the trees. We study the following problems: (1) What is the maximum capacity multi-tree solutions can exploit from overlay networks? (2) When multiple sessions compete within the same network, what is the relationship of two contradictory goals: achieving fairness and maximizing overall throughput? (3) What is the impact of IP routing in achieving at constraining the optimal performance of overlay multicast.We extend the multicommodity flow model to the case of overlay data dissemination, where each commodity is associated with an overlay session, rather than the traditional source-destination pair. We first prove that the problem is solvable in polynomial time, then propose an ε-approximation algorithm, assuming that each commodity can be split in arbitrary ways. The solution to this problem establishes the theoretical upper bound of overall throughput that any multi-tree solution could reach. We then study the same problem with the restriction that each commodity can only be split and fed into a limited number of trees. A randomized rounding algorithm and an online tree-construction algorithm are presented. All these algorithms are evaluated by extensive simulations.
5536365
Simulation of Diabetic Retinopathy Neovascularization in Color Digital Fundus Images
Diabetic retinopathy (DR) has been identified as a leading cause of blindness. One type of lesion, neovascularization (NV), indicates that the disease has entered a vision-threatening phase. Early detection of NV is thus clinically significant. Efforts have been devoted to use computer-aided analyses of digital retina images to detect DR. However, developing reliable NV detection algorithms requires large numbers of digital retinal images to test and refine approaches. Computer simulation of NV offers the potential of developing lesion detection algorithms without the need for large image databases of real pathology. In this paper, we propose a systematic approach to simulating NV. Specifically, we propose two algorithms based on fractal models to simulate the main structure of NV and an adaptive color generation method to assign photorealistic pixel values to the structure. Moreover, we develop an interactive system that provides instant visual feedback to support NV simulation guided by an ophthalmologist. This enables us to combine the low level algorithms with high-level human feedback to simulate realistic lesions. Experiments suggest that our method is able to produce simulated NVs that are indistinguishable from real lesions.
46149042
Data reconciliation for real-time optimization of an industrial coke-oven-gas purification process
Online optimization is more and more used in the chemical industry to run a process near its optimum operating condition by providing real-time computed optimal set-points to the distributed control system. Process measurements are necessary for these applications to determine the actual state of the process and to increase the accuracy of the model with parameter estimation techniques. However, these measurements usually contain random as well as gross errors which have to be identified and eliminated before the measurements are used for online optimization. In this contribution, a data reconciliation approach was integrated into an online optimization framework for the ammonia hydrogen sulfide circulation scrubbing, a common industrial coke-oven-gas purification process. We used a rigorous rate-based model to describe this reactive absorption and desorption process. To increase the accuracy of the model, we estimated several process parameters using a sequential parameter estimation approach. Data reconciliation was performed based on simple component balances to achieve model-consistent data and to identify measurement biases. The model was then validated online on a pilot plant by connecting the estimation package through the process control system. Based on the online measured data, operating cost minimization was carried out and the computed optimal set-points realized real-time. A satisfactory agreement between measured data and optimization was achieved.
1669054
Nonconforming finite element approximation of crystalline microstructure
We consider a class of nonconforming nite element approxima- tions of a simply laminated microstructure which minimizes the nonconvex variational problem for the deformation of martensitic crystals which can un- dergo either an orthorhombic to monoclinic (double well) or a cubic to tetrag- onal (triple well) transformation. We rst establish a series of error bounds in terms of elastic energies for the L 2 approximation of derivatives of the de- formation in the direction tangential to parallel layers of the laminate, for the L 2 approximation of the deformation, for the weak approximation of the de- formation gradient, for the approximation of volume fractions of deformation gradients, and for the approximation of nonlinear integrals of the deformation gradient. We then use these bounds to give corresponding convergence rates for quasi-optimal nite element approximations.