5555321
A hardware implementation of realloc function
Abstract The memory intensive nature of object-oriented languages such as C++ and Java has created the need of a high-performance dynamic memory management. Object-oriented applications often generate higher memory intensity in the heap region. Thus, high-performance memory manager is needed to cope with such applications. As today's VLSI technology advances, it becomes more and more attractive to map basic software algorithms such as malloc( ) , free( ) , and realloc( ) into hardware. This paper presents a hardware design of realloc function that fully utilizes the advantage of combinational logic. There are two steps needed to complete a reallocation process: (a) try to reallocate on the original memory block and (b) if (a) failed, allocate another memory block and copy the contents of the original block to this new location. In our scheme, (a) can be done in constant time. For (b), the allocation of new memory block and the deallocation of original block are done in constant time. The hardware complexity of proposed scheme (i.e. X-unit , RS-unit , and ESG-unit ) is O ( n ), where n represents the size of bit-map.
46189070
Optimal use of timing resources: a crucial step in test program generation
A modified timing set priority strategy and a lookahead register-replacement algorithm is presented for automatic test program generation. These methodologies are introduced to satisfy the testing requirements in complex VLSI chips, and are made possible by the increasing timing flexibility of modern ATE (automatic test equipment). It is shown that by applying optimization algorithms in allocating timing resources and a published timing set determination algorithm, that testing capability of modern ATE can be greatly extended. Further enhancements to these approaches are contingent on further improvements from ATE manufacturers in the number and flexibility of timing resources. However, the development of test programs will be greatly aided by this enhanced hardware.<<ETX>>
18001825
Architectural support for dynamic memory management
Recent advances in software engineering, such as graphical user interfaces and object-oriented programming, have caused applications to become more memory intensive. These applications tend to allocate dynamic memory prolifically. Moreover, automatic dynamic memory reclamation (garbage collection, GC) has become a popular feature in modern programming languages. As a result, the time consumed by dynamic storage management can be up to one-third of the program execution time. This illustrates the need for a high-performance memory management scheme. This paper presents a top-level design and evaluation of the proposed instruction extensions to facilitate heap management.
9645285
Using scratchpad to exploit object locality in Java
Performance of modern computers is tied closely to the effective use of cache because of the continually increasing speed discrepancy between processors and main memory. We demonstrate that generational garbage collection employed by a system with cache and scratchpad memory can take advantage of the locality of small short-lived objects in Java and reduce memory traffic by as much as 20% when compared to a cache-only configuration. Converting half of the cache to scratchpad can be more effective at reducing memory traffic than doubling or even quadrupling the size of the cache for several of the applications in SPECjvm98.
12416012
An efficient data structure for dynamic memory management
Abstract Advances in software engineering, such as graphical user interface and object-oriented programming, have caused applications to become more memory intensive. The growing popularity of these applications increases the importance of high-performance dynamic memory management. This paper introduces a new data structure intended to increase the efficiency of implementations of common dynamic memory allocation and deallocation algorithms, including First Fit . The data structure, called the Common List , establishes a relationship between the allocated and free list. This strategy increases significantly the deallocation performance. Simulation results based on the traces from publicly available software applications are presented.
1021056
A performance perspective on the Active Memory System
Abstract One major problem of using Java in real-time and embedded devices is the non-deterministic turnaround time of dynamic memory management systems (memory allocation and garbage collection). For the allocation, the non-determinism is often contributed by the time to perform searching, splitting, and coalescing. For the garbage collection, the turnaround time is usually determined by the size of the heap, the number of live objects, the number of object collected, and the amount of garbage collected. Even with the current state-of-the-art garbage collectors (generational and incremental schemes), they may or may not guarantee the worst-case latency. Moreover, such schemes often prolong overall garbage collection time. In this paper, the performance analysis of the proposed Active Memory Module (AMM) for embedded systems is presented. Unlike the software counterparts, the AMM can perform a memory allocation in a predictable and bounded fashion (14 cycles). Moreover, it can also yield a bounded sweeping time regardless of the number of live objects or heap size. By utilizing the proposed system, the overall speedup can be as high as 23% compared to the garbage collection system of the JDK 1.2.2 running in classic mode.
9345376
Finding recently frequent itemsets adaptively over online transactional data streams,
A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Consequently, the knowledge embedded in a data stream is more likely to be changed as time goes by. Identifying the recent change of a data stream, especially for an online data stream, can provide valuable information for the analysis of the data stream. However, most of mining algorithms or frequency approximation algorithms over a data stream do not differentiate the information of recently generated data elements from the obsolete information of old data elements which may be no longer useful or possibly invalid at present. Therefore, they are not able to extract the recent change of information in a data stream adaptively. This paper proposes a data mining method for finding recently frequent itemsets adaptively over an online transactional data stream. The effect of old transactions on the current mining result of a data steam is diminished by decaying the old occurrences of each itemset as time goes by. Furthermore, several optimization techniques are devised to minimize processing time as well as memory usage. Finally, the performance of the proposed method is analyzed by a series of experiments to identify its various characteristics.
34947079
On the powers of graphs with bounded asteroidal number
Abstract For an undirected graph G =( V , E ), the kth power G k is the graph with the same vertex set as G such that two vertices are adjacent in G k if and only if their distance in G is at most k. A set of vertices A ⊆ V is an asteroidal set if for every vertex a ∈ A , the set A ⧹{ a } is contained in one connected component of G − N G [ a ], where N G [ a ] is the closed neighborhood of a in G. The asteroidal number of a graph G is the maximum cardinality of an asteroidal set in G. The class of graphs with asteroidal number at most s is denoted by A (s) . In this paper, we show that if G k ∈ A (s) for s ⩾2, then so is G k +1 . This generalizes a previous result for the family of AT-free graphs. Moreover, we consider the forbidden configurations for the powers of graphs with bounded asteroidal number. Based on these forbidden configurations, we show that every proper power of AT-free graphs is perfect.
37599184
Finding frequent itemsets over online data streams
Abstract Conventional data mining methods for finding frequent itemsets require considerable computing time to produce their results from a large data set. Due to this reason, it is almost impossible to apply them to an analysis task in an online data stream where a new transaction is continuously generated at a rapid rate. An algorithm for finding frequent itemsets over an online data stream should support flexible trade-off between processing time and mining accuracy. Furthermore, the most up-to-date resulting set of frequent itemsets should be available quickly at any moment. To satisfy these requirements, this paper proposes a data mining method for finding frequent itemsets over an online data stream. The proposed method examines each transaction one-by-one without any candidate generation process. The count of an itemset that appears in each transaction is monitored by a lexicographic tree resided in main memory. The current set of monitored itemsets in an online data stream is minimized by two major operations: delayed-insertion and pruning . The former is delaying the insertion of a new itemset in recent transactions until the itemset becomes significant enough to be monitored. The latter is pruning a monitored itemset when the itemset turns out to be insignificant. The number of monitored itemsets can be flexibly controlled by the thresholds of these two operations. As the number of monitored itemsets is decreased, frequent itemsets in the online data stream are more rapidly traced while they are less accurate. The performance of the proposed method is analyzed through a series of experiments in order to identify its various characteristics.
261727
Guaranteed Quality-of-Service Wireless Access to ATM Networks
We study the problem of wireless access to asynchronous transfer modes (ATMs). We consider three classes of ATM sources: constant bit rate (CBR), variable bit rate (VBR), and available bit rate (ABR). We propose a polling scheme with nonpreemptive priority. Under such a scheme, we derive sufficient conditions such that all the CBR sources satisfy their jitter constraints and all the VBR sources satisfy their delay constraints. The remaining bandwidth is used by the ABR sources, for which we adapt a random access scheme proposed by Chen and Lee (1994). For this random access scheme, we derive the throughput-offer load characteristic, and thus the capacity. Based on this, we propose adaptive random access schemes that track the offer load to its optimal value. Our simulations show that our adaptive schemes maintain a high throughput with respect to the whole range of system load.
38826941
Effect of Count Estimation in Finding Frequent Itemsets over Online Transactional Data Streams
A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Due to this reason, most algorithms for data streams sacrifice the correctness of their results for fast processing time. The processing time is greatly influenced by the amount of information that should be maintained. This issue becomes more serious in finding frequent itemsets or frequency counting over an online transactional data stream since there can be a large number of itemsets to be monitored. We have proposed a method called theestDec method for finding frequent itemsets over an online data stream. In order to reduce the number of monitored itemsets in this method, monitoring the count of an itemset is delayed until its support is large enough to become a frequent itemset in the near future. For this purpose, the count of an itemset should be estimated. Consequently, how to estimate the count of an itemset is a critical issue in minimizing memory usage as well as processing time. In this paper, the effects of various count estimation methods for finding frequent itemsets are analyzed in terms of mining accuracy, memory usage and processing time.