[go: up one dir, main page]

Zhong et al., 1991 - Google Patents

Parallel Implementation of Divide-and-Conquer Algorithms on Binary de Bruijn Networks.

Zhong et al., 1991

View PDF
Document ID
4419057100086980803
Author
Zhong X
Rajopadhye S
Lo V
Publication year

External Links

Snippet

We study the problem of parallel implementation of divide-and-conquer algo-rithms on binary de Bruijn network. We model the divide-and-conquer algorithm as a temporal binomial tree computation structure which we show to be an efficient structure for this type of …
Continue reading at www.cs.uoregon.edu (PDF) (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
    • 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
    • G06F17/30958—Graphs; Linked lists
    • 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
    • G06F17/30961—Trees
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q3/00—Selecting arrangements
    • H04Q3/64—Distributing or queueing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/12—Arrangements for maintenance or administration or management of packet switching networks network topology discovery or management

Similar Documents

Publication Publication Date Title
US5134690A (en) Augumented multiprocessor networks
US7280481B2 (en) Shortest path search method “Midway”
Yang et al. Embedding of rings and meshes onto faulty hypercubes using free dimensions
JPH05181821A (en) Method for connecting plurality of nodes in nonbinary-hyper-cube type computer system and network
Blelloch et al. An experimental analysis of parallel sorting algorithms
Cidon et al. New models and algorithms for future networks
Das et al. A new network topology with multiple meshes
Abali et al. Balanced parallel sort on hypercube multiprocessors
Valiant Optimality of a two-phase strategy for routing in interconnection networks
Liszka et al. Problems with comparing interconnection networks: Is an alligator better than an armadillo?
Zhong et al. Parallel Implementation of Divide-and-Conquer Algorithms on Binary de Bruijn Networks.
Leu et al. Distributed fault-tolerant ring embedding and reconfiguration in hypercubes
Ziavras et al. Pyramid mappings onto hypercubes for computer vision: Connection machine comparative study
Das et al. Stirling networks: a versatile combinatorial topology for multiprocessor systems
Hamdi et al. An efficient class of interconnection networks for parallel computations
Thakur et al. Complete exchange on the CM-5 and Touchstone Delta
Ho et al. Efficient broadcast on hypercubes with wormhole and e-cube routings
Chen et al. Fault-tolerant routing for pyramid networks using the least level minimal routing method
Chen et al. A general broadcasting scheme for recursive networks with complete connection
Wu et al. Cube-connected-cubes network
Huang et al. An improved topology discovery algorithm for networks with wormhole routing and directed links
Somani et al. The helical cube network
Dhelaan Processor allocation & communication in networks
KAWAGUCHI et al. A Task Mapping Algorithm for Linear Array Processors
Chen Shuffle-X graphs and their cayley variants