Search

Ternary content-addressable memories (TCAMs) can perform high-speed and deterministic table lookups. However, its main drawback is high power consumption. A significant portion of the TCAM power is consumed by match-line sense amplifiers (MLSAs) for match detection. This paper presents a 20-kilobit TCAM featuring two MLSAs with positive-feedback techniques. The proposed circuits have been fabricated on a test chip in 0.18-[micro]m CMOS technology. Energy measurement results of the two MLSAs show reductions of 56% and 48%, respectively, over the conventional current-race MLSA. Index Terms--Associative memories, content-addressable memory, feedback circuits, match-line sense amplifiers (MLSAs).

This paper presents the implementation of a video segmentation unit used for embedded automated video surveillance systems. Various aspects of the underlying segmentation algorithm are explored and modifications are made with potential improvements of segmentation results and hardware efficiency. In addition, to achieve real-time performance with high resolution video streams, a dedicated hardware architecture with streamlined dataflow and memory access reduction schemes are developed. The whole system is implemented on a Xilinx field-programmable gate array platform, capable of real-time segmentation with VGA resolution at 25 frames per second. Substantial memory bandwidth reduction of more than 70% is achieved by utilizing pixel locality as well as wordlength reduction. The hardware platform is intended as a real-time testbench, especially for observations of long term effects with different parameter settings. Index Terms--Field-programmable gate array (FPGA), mixture of Gaussian (MoG), video segmentation.

The need to carefully schedule memory operations has increased as memory performance has become increasingly important to overall system performance. This article describes the adaptive history-based (AHB) scheduler, which uses the history of recently scheduled operations to provide three conceptual benefits: (1) it allows the scheduler to better reason about the delays associated with its scheduling decisions, (2) it provides a mechanism for combining multiple constraints, which is important for increasingly complex DRAM structures, and (3) it allows the scheduler to select operations so that they match the program's mixture of Reads and Writes, thereby avoiding certain bottlenecks within the memory controller. We have previously evaluated this scheduler in the context of the IBM Power5. When compared with the state of the art, this scheduler improves performance by 15.6%, 9.9%, and 7.6% for the Stream, NAS, and commercial benchmarks, respectively. This article expands our understanding of the AHB scheduler in a variety of ways. Looking backwards, we describe the scheduler in the context of prior work that focused exclusively on avoiding bank conflicts, and we show that the AHB scheduler is superior for the IBM Power5, which we argue will be representative of future microprocessor memory controllers. Looking forwards, we evaluate this scheduler in the context of future systems by varying a number of microarchitectural features and hardware parameters. For example, we show that the benefit of this scheduler increases as we move to multithreaded environments. Categories and Subject Descriptors: C.1.1 [Processor Architectures]: Single Data Stream Architectures General Terms: Performance Additional Key Words and Phrases: Memory system performance, memory scheduling, adaptive history-based scheduling

The article presents the Martini designed as a network interface controller chip in which communication functions are implemented by hardwired logic. Martini provides maximum bandwidth and minimum latency communication.

We investigate the maximum increase in number of phrases that results from changing k consecutive symbols in a string x having length n parsed using an LZ'77-like algorithm. We consider a class of compression algorithms that partition a sequence into a collection y of nonoverlapping, variable-length phrases and encode them. Each phrase either is a singleton or matches a substring that starts to its left. We show that changing a single symbol of [??] in position i can yield an expansion that is of order O[(n - i).sup.2/3] as (n - i) [right arrow] [infinity]. Our lower bound requires an alphabet size of O[(n - i)sup.1/3]. We also show that changing k consecutive symbols starting from position I can yield an expansion having a similar but somewhat more involved form. The paper contains both analytically derived upper and lower bounds, and algorithms for numerically computing tighter bounds. While deriving the bounds, we provide a detailed analysis of how expansion can arise when changing consecutive symbols. This problem is motivated by management policies for computer systems, such as the IBM Memory eXpansion Technology (MXT) or the IBM iSeries compressed disks, that use LZ'77-like coding on small compression units, such as 1-4 kbyte, and store the compressed data in memory or on disk tracks. Here, when a change of a portion of the compression unit occurs, for example, an L2 cache line, or a 512-byte disk sector, the data is recompressed and potentially stored in a different location. Knowing the maximum expansion, rather than the average expansion, is an important factor for designing policies for allocation and management of memory or disk space.

Aggressive prefetching mechanisms improve performance of some important applications, but substantially increase bus traffic and "pressure" on cache tag arrays. They may even reduce performance of applications that are not memory bounded. We introduce a "feedback" mechanism, termed Prefetcher Assessment Buffer (PAB), which filters out requests that are unlikely to be useful. With this, applications that cannot benefit from aggressive prefetching will not suffer from their side-effects. The PAB is evaluated with different configurations, e.g., "all L1 accesses trigger prefetches" and "only misses to L1 trigger prefetches". When compared with the non-selective concurrent use of multiple prefetchers, the PAB's application to prefetching from main memory to the L2 cache can reduce the number of loads from main memory by up to 25% without losing performance. Application of more sophisticated techniques to prefetches between the L2- and L1-cache can increase IPC by 4% while reducing the traffic between the caches 8-fold. KEY WORDS: Prefetching; cache tag pressure; memory wall.

The bandwidth mismatch between processor and main memory is one major throughput limiting problem. Although streamed computations have predictable access patterns their references have little temporal locality and are generally too long to cache. A memory and compiler co-optimization aimed at reducing low-level memory accesses using software and hardware locality optimizations is presented. We propose a scalable and predictable parallel memory based on a compiler synthesis of storage schemes for multi-dimensional arrays that are accessed by an arbitrary but known set of data access patterns. Using algebra of non-singular Boolean matrices, we present analysis of conflict-free access to (1) parallel memories, and (2) alignment networks. Finding a multi-pattern storage scheme is one NP-complete problem. An effective compiler heuristic is proposed for finding a storage matrix that minimizes overall memory access time. This applies to arbitrary linear patterns and arbitrary alignment networks. It is shown that the proposed storage scheme finds an optimal storage scheme for parallel (1) FFT, and (2) bitonic sorting. The proposed storage scheme outperforms statically optimized storages in the case of power-of-2 multi-stride access. The case of non power-of-2 strides is also addressed. The performance and scalability of the proposed parallel memory and its predictable access time are presented using numerical and multimedia algorithms. It is shown that a memory utilization above 83% is achieved by our storage scheme for 64 memories, which largely outperforms previous proposals. Our approach provides a tool for matching the storage pattern with the data access patterns needed for embedded systems running streamed computations with predictable data access patterns. KEY WORDS: Access patterns; embedded systems; compiler optimization; parallel memory; streamed computations.

Analyses of the necessity of framework preconstruction, aggregate storage subsumption and predictive storage preallocation, which are three memory management optimizations, indicate their usage in SISAL 1.2 programs, which help array construction. These optimizations remove the allocate-deallocate sequences, decrease the array component's management overhead and simplify and remove data copying in filtered arrays.

A parallel garbage collection (GC) algorithm written in a concurrent programming language, KL1, with a stop-and-copy sequential algorithm is analyzed for its performance characteristics. It activates when half the available processor memory space is used up. The algorithm performs most memory accesses without mutual exclusion, thus negating the need for locking during cell copying. GC techniques run on a fifth generation multiprocessor designed for high-level parallel languages such as Lisp.

Update technique is an important issue related to database recovery. In a main memory database environment, transaction execution can be processed without any I/O, and all I/O operations involved are for recovery purposes. The efficiency of update techniques therefore has an important impact on the performance of main memory database systems. In this paper, we compared the techniques of immediate and deferred update based on a database machine, MARS. The simulation results showed that immediate update outperforms deferred update unless system failure is a frequent occurrence. Index Terms - Main memory databases, update, failure recovery, transaction processing, simulation.