In this paper, a memory system is introduced for the efficient construction of a Gaussian pyramid. The memory system consists of an address calculating circuit, an address routing circuit, a memory module selection circuit, and 2/sup n/+1 memory modules. The memory system provides parallel access to 2/sup n/ image points whose patterns are a block, a row or a column, where the interval of the column and the block is 1 and the interval of the row is 2/sup l/,l/spl ges/0. The performance of a generic SIMD (single-instruction multiple-data) processor using the proposed memory system is compared with one using an interleaved memory system for the construction of a Gaussian pyramid. The ratio of the time of the construction of level 2 and level 10 from the original image (level 0) of an SIMD processor with an interleaved memory system to that of the proposed memory system is 1.485 and 1.633, respectively.

Algorithms for constructing differential images with hierarchical data structure are presented. The data structures are simple, efficient, and ideal for viewing images in progressive transmission using lossless compression. Unlike conventional pyramidal structures, the total number of nodes required to build the structure is the same as the number of pixels in an image at the same time its hierarchy is preserved. These structures are constructed using subsampling or mean-sampling methods for predictors with block sizes of 2/spl times/2 or 3/spl times/3. Experiments were conducted to compare these structures in terms of their first order entropy and RMS errors in the reconstruction process. Results indicate that the mean-sampling with circular-difference method yields the lowest entropy, comparable to that with 1-D lossless DPCM predictive coding. Lastly, hardware for the efficient construction and access of the hierarchical structures is discussed and evaluated.>

Many current graphical display systems are based around a memory array commonly known as a frame buffer. In these systems, the frame buffer contains the array of pixels currently being displayed. Updates to the display are accomplished by modifying the values in the frame buffer. The author demonstrates how the performance of frame buffer based systems can be improved by decreasing the number of accesses to the frame buffer memory array. The proposed architecture, referred to as a multiaccess frame buffer, allows parallel access to constant area rectangles of the array of pixels stored in the frame buffer rather than the row oriented accesses required by most current frame buffer architectures. By allowing more general types of access, a given update can be performed with fewer frame buffer accesses.>

A limiting factor in high-performance vector computers is the rate at which data can be moved to and from memory during vector loads and stores. To increase the bandwidth of vector memory operations, several investigators have proposed the use of noninterleaved storage mappings, also known as storage schemes. A method of analyzing the performance of vector references for the class of storage schemes referred to as XOR schemes is described. The proposed measure of relative performance, the variability of an access, is defined and its computation is outlined. The use of variability as a performance indicator is demonstrated and compared with performance measurements made using simulation. One of the key aspects of the variability measure is its capability to lend insight to the transient behavior of vector accesses.>

A technique to analyze transformation matrices is presented. This technique is based on decomposing complex transformations into elementary transformations. When combined with a factorization of the access stride into two components, one a power of 2 and the other relatively prime to 2, the technique leads to an algorithmic synthesis of a CF (conflict free) storage scheme. Additionally, because the address to storage location mapping arithmetic is performed modulo 2, the time required to transform an address to its corresponding storage location is smaller and the hardware cost is lower than if schemes based on row rotation were used.>

Article Reducing memory contention in shared memory multiprocessors Share on Author: D. T. Harper Department of Electrical Engineering, The University of Texas at Dallas, P.O. Box 830688, MP 33, Richardson, Texas Department of Electrical Engineering, The University of Texas at Dallas, P.O. Box 830688, MP 33, Richardson, TexasView Profile Authors Info & Claims ISCA '91: Proceedings of the 18th annual international symposium on Computer architectureApril 1991 Pages 66–73https://doi.org/10.1145/115952.115960Online:01 April 1991Publication History 1citation358DownloadsMetricsTotal Citations1Total Downloads358Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An approach whereby conflict-free access of any constant stride can be made by selecting a storage scheme for each vector based on the accessing patterns used with that vector is considered. By factoring the stride into two components, one a power of 2 and the other relatively prime to 2, a storage scheme that allows conflict-free access to the vector using the specified stride can be synthesized. All such schemes are based on a variation of the row rotation mechanism proposed by P. Budnik and D. Kuck (ibid., vol.C-20. no.12, pp.1566-9, Dec. 1971). Each storage scheme is based on two parameters, one describing the type of rotation to perform and the other describing the amount of memory to be rotated as a single block. The performance of the memory under access strides other than the stride used to specify the storage scheme is also considered. Modeling these other strides represents a vector being accessed with multiple strides as well as situations when the stride cannot be determined prior to initializing the vector. Simulation results show that if a single buffer is added to each memory port, then the average performance of the dynamic scheme surpasses that of the interleaved scheme for arbitrary stride accesses.>

A discussion is presented of the use of dynamic storage schemes to improve parallel memory performance during three important classes of data accesses: vector accesses in which multiple strides are used to access a single vector, block accesses, and constant-geometry FFT accesses. The schemes investigated are based on linear address transformations, also known as XOR schemes. It has been shown that this class of schemes can be implemented more efficiently in hardware and has more flexibility than schemes based on row rotations or other techniques. Several analytical results are shown. These include: quantitative analysis of buffering effects in pipelined memory systems; design rules for storage schemes that provide conflict-free access using multiple strides, blocks, and FFT access patterns; and an analysis of the effects of memory bank cycle time on storage scheme capabilities.>

Previous investigations into data storage schemes have focused on finding a storage scheme that permits conflict-free access for a set of frequently encountered access patterns. This paper considers an alternative approach. Rather than forcing a single storage scheme to be used for all access patterns, conflict-free accesses of any constant stride can be made by selecting a storage scheme for each vector based on the accessing patterns used with that vector.

This paper presents and evaluates a class of buffered interconnection networks which provide performance and cost levels intermediate to a bus and a delta network. These networks, referred to as hybrid networks, are formed by beginning with a delta network and substituting buses for the final stages of the network. The choice of the number of stages replaced determines the bandwidth of the network. The reduction of network bandwidth is accompanied by a corresponding reduction in network cost. Hybrid networks provide the system architect with a cost-effective solution to design problems in which the required interconnection bandwidth is greater than that of a bus but less than that of a full delta network.

The degree to which high-speed vector processors approach their peak performance levels is closely tied to the amount of interference they encounter while accessing vectors in memory. In this paper we present an evaluation of a storage scheme that reduces the average memory access time in a vector-oriented architecture. A skewing scheme is used to map vector components into parallel memory modules such that, for most vector access patterns, the number of memory conflicts is reduced over that observed in interleaved parallel memory systems. Address and data buffers are used locally in each module so that transient nonuniformities which occur in some access patterns do not degrade performance. Previous investigations into skewing techniques have attempted to provide conflict-free access for a limited subset of access patterns. The goal of this investigation is different. The skewing scheme evaluated here does not eliminate all memory conflicts but it does improve the average performance of vector access over interleaved systems for a wide range of strides. It is shown that little extra hardware is required to implement the skewing scheme. Also, far fewer restrictions are placed on the number of memory modules in the system than are present in other proposed schemes.

This paper presents and evaluates a scheme for reducing the average memory access time in a vector processing architecture. This scheme uses data skewing to distribute vectors among the modules of a parallel memory system in such a way that, for typical vector access patterns, the average number of memory conflicts is reduced. It also employs both address and data buffers in each module to smooth out the transient irregularities that occur in some vector access patterns. Most previous data skewing techniques were developed to provide conflict-free access for a limited set of access strides. While the proposed scheme does not eliminate all conflicts, it improves the average performance over non-skewed parallel memories by significantly reducing the number of conflicts for a wide range of strides. Also, this effect is much less dependent on the number of memory modules than the skewing schemes used to obtain conflict-free access.