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

Abali et al., 1993 - Google Patents

Balanced parallel sort on hypercube multiprocessors

Abali et al., 1993

Document ID
1724686014839311364
Author
Abali B
Ozguner F
Bataineh A
Publication year
Publication venue
IEEE Transactions on Parallel and Distributed Systems

External Links

Snippet

A parallel sorting algorithm for sorting n elements evenly distributed over 2/sup d/p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O ((n log n)/p+ p log 2n). The algorithm maintains a perfect load balance in the nodes by …
Continue reading at ieeexplore.ieee.org (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/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/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
    • G06F15/17381—Two dimensional, 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/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
    • 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/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • 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/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • 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
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
Abali et al. Balanced parallel sort on hypercube multiprocessors
Thompson et al. Sorting on a mesh-connected parallel computer
Reif et al. A logarithmic time sort for linear size networks
Schnorr et al. An optimal sorting algorithm for mesh connected computers
JP2512661B2 (en) Non-binary hypercube type computer system and network connection method for multiple nodes
Blelloch et al. An experimental analysis of parallel sorting algorithms
Cypher Theoretical aspects of VLSI pin limitations
Won et al. A balanced bin sort for hypercube multicomputers
Rajasekaran et al. Constant queue routing on a mesh
Chen Efficient parallel binary search on sorted arrays, with applications
Chin et al. Connection principles for multipath, packet switching networks
Bratbergsengen et al. A neighbor connected processor network for performing relational algebra operations
Abali et al. Load balanced sort on hypercube multiprocessors
Baru et al. Join and data redistribution algorithms for hypercubes
Krizanc Integer sorting on a mesh-connected array of processors
Chang et al. Continuous routing and batch routing on the hypercube
Rajasekaran et al. Randomized parallel computation
Hamdi et al. RCC-full: An effective network for parallel computations
Monien et al. A realizable efficient parallel architecture
Kruskal Upper and lower bounds on the performance of parallel algorithms
Lan et al. Parallel quicksort in hypercubes
Rooks et al. A unifying Framework for Distributed Routing Algorithms.
Li et al. Parallel sorting on Symult 2010
Valero-Garcia et al. Systematic hardware adaptation of systolic algorithms
An et al. Optimal Algorithms for a Mesh-Connected Computer with Limited Additional Global Bandwidth