Search

Dynamic Spectrum Access systems offer temporarily available spectrum to opportunistic users capable of spreading transmissions over a number of non-contiguous subchannels. Such methods can be highly beneficial in terms of spectrum utilization, but excessive fragmentation degrades performance and hence off-sets the benefits. To get some insight into acceptable levels of fragmentation, we present experimental and analytical results derived from a mathematical model. According to the model, a system operates at capacity serving requests for bandwidth by assigning a collection of one or more gaps of unused bandwidth to each request as bandwidth becomes available. Our main result is a proof that, even if fragments can be arbitrarily small, the system remains stable in the sense that the average total number of fragments remains bounded. Within the class of dynamic fragmentation models, including models of dynamic storage allocation that have been around for many decades, this result appears to be the first of its kind. In addition, we provide extensive experimental results that describe behavior, at times unexpected, of fragmentation as parameter values are varied. Different scanning rules for searching gaps of available spectrum, all covered by the above stability result, are also studied. Our model applies to dynamic linked-list storage allocation, and provides a novel analysis in that domain. We prove that, interestingly, a version of the 50 % rule of the classical, non-fragmented allocation model holds for the new model as well. Overall, the paper provides insights into the behavior of practical fragmentation algorithms. [ABSTRACT FROM AUTHOR]

Interaction between the phases of register allocation and instruction scheduling are often considered in publications devoted to optimizations for the final stage of compilation. Typically, it is proposed to adapt one of the phase for needs of another without their combination into a single unit. However, their integration can essentially reduce the time of operation and enhance the performance of the resulting code. This study describes an attempt to combine these phases as completely as possible with account for the features of static scheduling for VLIW-architectures. [ABSTRACT FROM AUTHOR]

A Modified Euclidean (ME) algorithm has been used to solve the key equations in Reed-Solomon (RS) decoding. In this article, the degree properties of the ME algorithm are derived. On the basis of the degree properties, an area-efficient very large scale integration (VLSI) architecture with dynamic storage technique is proposed to perform the ME algorithm. The dynamic storage technique is used to avoid data exchange and save hardware resources. The proposed architecture with dynamic storage technique can reduce 50% computation hardware area and about 30% memory hardware area. VLSI implementation results of different RS codes show that the proposed architecture is significantly area-efficient, especially for RS codes with long code lengths. [ABSTRACT FROM AUTHOR]

With the diverging improvements in CPU speeds and memory access latencies, detecting and removing memory access bottlenecks becomes increasingly important. In this work we present METRIC, a software framework for isolating and understanding such bottlenecks using partial access traces. METRIC extracts access traces from executing programs without special compiler or linker support. We make four primary contributions. First, we present a framework for extracting partial access traces based on dynamic binary rewriting of the executing application. Second, we introduce a novel algorithm for compressing these traces. The algorithm generates constant space representations for regular accesses occurring in nested loop structures. Third, we use these traces for offline incremental memory hierarchy simulation. We extract symbolic information from the application executable and use this to generate detailed source-code correlated statistics including per-reference metrics, cache evictor information, and stream metrics. Finally, we demonstrate how this information can be used to isolate and understand memory access inefficiencies. This illustrates a potential advantage of METRIC over compile-time analysis for sample codes, particularly when interprocedural analysis is required. [ABSTRACT FROM AUTHOR]

Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT ≥ LOAD; previous work showed that OPT < 3 LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT = L + O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any &epsiv; > 0, there exists a c > 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+&epsiv;L, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + &epsiv;)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]

It is demonstrated how dynamic storage allocation algorithms can be analyzed in terms of finite-size scaling. The method is illustrated in the three simple cases of the first-fit, next-fit and best-fit algorithms, and the system works at full capacity. The analysis is done from two different points of view—running speed and employed memory. In both cases, and for all algorithms, it is shown that a simple scaling function exists and the relevant exponents are calculated. The method can be applied on similar problems as well. [Copyright &y& Elsevier]