Nothing Special   »   [go: up one dir, main page]

Merry et al., 1995 - Google Patents

A constant time sorting algorithm for a three dimensional reconfigurable mesh and reconfigurable network

Merry et al., 1995

Document ID
9691182789706863458
Author
Merry M
Baker J
Publication year
Publication venue
Parallel Processing Letters

External Links

Snippet

Sorting techniques have numerous applications in computer science. Current real number and integer sorting techniques for the reconfigurable mesh operate in constant time using a reconfigurable mesh of size n× n to sort n numbers. This paper presents a constant time …
Continue reading at www.worldscientific.com (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored programme computers
    • G06F15/80—Architectures of general purpose stored programme computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
    • G06F15/8007—Architectures of general purpose stored programme computers comprising an array of processing units with common control, e.g. single instruction multiple data processors single instruction multiple data [SIMD] multiprocessors
    • G06F15/8023—Two dimensional arrays, e.g. mesh, torus
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17356—Indirect interconnection networks
    • G06F15/17368—Indirect interconnection networks non hierarchical topologies
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17337—Direct connection machines, e.g. completely connected computers, point to point communication networks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored programme computers
    • G06F15/78—Architectures of general purpose stored programme computers comprising a single central processing unit
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/76—Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design

Similar Documents

Publication Publication Date Title
Feng A survey of interconnection networks
Lin et al. Algorithmic mapping of neural network models onto parallel SIMD machines
Das et al. A new network topology with multiple meshes
KR100373426B1 (en) Digital processing device
Olariu et al. Fast computer vision algorithms for reconfigurable meshes
Serrano et al. Optimal architectures and algorithms for mesh-connected parallel computers with separable row/column buses
Lin et al. Simulating enhanced meshes, with applications
Olariu et al. Integer problems on reconfigurable meshes, with applications
JP3977880B2 (en) Programmable gate array operation method
Merry et al. A constant time sorting algorithm for a three dimensional reconfigurable mesh and reconfigurable network
Nakano Optimal initializing algorithms for a reconfigurable mesh
Ziavras et al. Pyramid mappings onto hypercubes for computer vision: Connection machine comparative study
Nakano et al. An optimal algorithm for the angle-restricted all nearest neighbor problem on the reconfigurable mesh, with applications
Raghavendra HMESH: A VLSI architecture for parallel processing
Wang et al. Parallel algorithms for arbitrary dimensional Euclidean distance transforms with applications on arrays with reconfigurable optical buses
Suel Permutation routing and sorting on meshes with row and column buses
Parhami et al. Robust shearsort on incomplete bypass meshes
Alnuweiri Fast algorithms for image labeling on a reconfigurable network of processors
Haendler et al. Vertical processing in parallel computing systems
Johnsson Ensemble architectures and their algorithms: an overview
Pan Order statistics on a linear array with a reconfigurable bus
International Neural Network Society (INNS), the IEEE Neural Network Council Cooperating Societies et al. Implementation of back-propagation on a VLSI asynchronous cellular architecture
Sinha et al. Parallel sorting algorithm using multiway merge and its implementation on a multi-mesh network
Chuang et al. An efficient Hough transform algorithm on SIMD hypercube
Biswas On bit steering in the minimization of the control memory of microprogrammed processors