Hypertree network

Last updated

A hypertree network is a network topology that shares some traits with the binary tree network. [1] It is a variation of the fat tree architecture. [2]

A hypertree of degree k depth d may be visualized as a 3-dimensional object whose front view is the top-down complete k-ary tree of depth d and the side view is the bottom-up complete binary tree of depth d. [1]

Hypertrees were proposed in 1981 by James R. Goodman and Carlo Sequin. [3]

Hypertrees are a choice for parallel computer architecture, used, e.g., in the connection machine CM-5. [2] [4]

Related Research Articles

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Binary space partitioning</span> Method for recursively subdividing a space into two subsets using hyperplanes

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

<span class="mw-page-title-main">Fat tree</span> Universal network for provably efficient communication

The fat tree network is a universal network for provably efficient communication. It was invented by Charles E. Leiserson of the Massachusetts Institute of Technology in 1985. k-ary n-trees, the type of fat-trees commonly used in most high-performance networks, were initially formalized in 1997.

<span class="mw-page-title-main">Z-order curve</span> Mapping function that preserves data point locality

In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It is named in France after Henri Lebesgue, who studied it in 1904, and named in the United States after Guy Macdonald Morton, who first applied the order to file sequencing in 1966. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used, such as simple one dimensional arrays, binary search trees, B-trees, skip lists or hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree or octree.

<span class="mw-page-title-main">Network on a chip</span> Electronic communication subsystem on an integrated circuit

A network on a chip or network-on-chip is a network-based communications subsystem on an integrated circuit ("microchip"), most typically between modules in a system on a chip (SoC). The modules on the IC are typically semiconductor IP cores schematizing various functions of the computer system, and are designed to be modular in the sense of network science. The network on chip is a router-based packet switching network between SoC modules.

In computer networking, if the network is bisected into two equal-sized partitions, the bisection bandwidth of a network topology is the bandwidth available between the two partitions. Bisection should be done in such a way that the bandwidth between two partitions is minimum. Bisection bandwidth gives the true bandwidth available in the entire system. Bisection bandwidth accounts for the bottleneck bandwidth of the entire network. Therefore bisection bandwidth represents bandwidth characteristics of the network better than any other metric.

<span class="mw-page-title-main">Intel iPSC</span>

The Intel Personal SuperComputer was a product line of parallel computers in the 1980s and 1990s. The iPSC/1 was superseded by the Intel iPSC/2, and then the Intel iPSC/860.

<span class="mw-page-title-main">Özalp Babaoğlu</span> Turkish computer scientist (born 1955)

Özalp Babaoğlu, is a Turkish computer scientist. He is currently professor of computer science at the University of Bologna, Italy. He received a Ph.D. in 1981 from the University of California at Berkeley. He is the recipient of 1982 Sakrison Memorial Award, 1989 UNIX InternationalRecognition Award and 1993 USENIX AssociationLifetime Achievement Award for his contributions to the UNIX system community and to Open Industry Standards. Before moving to Bologna in 1988, Babaoğlu was an associate professor in the Department of Computer Science at Cornell University. He has participated in several European research projects in distributed computing and complex systems. Babaoğlu is an ACM Fellow and has served as a resident fellow of the Institute of Advanced Studies at the University of Bologna and on the editorial boards for ACM Transactions on Computer Systems, ACM Transactions on Autonomous and Adaptive Systems and Springer-Verlag Distributed Computing.

Franco P. Preparata is a computer scientist, the An Wang Professor, Emeritus, of Computer Science at Brown University.

<span class="mw-page-title-main">Clyde Kruskal</span> American computer scientist

Clyde P. Kruskal is an American computer scientist, working on parallel computing architectures, models, and algorithms. As part of the ultracomputer project, he was one of the inventors of the read–modify–write concept in parallel and distributed computing. He is an associate professor of computer science at the University of Maryland, College Park.

<span class="mw-page-title-main">Cube-connected cycles</span> Undirected cubic graph derived from a hypercube graph

In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by Preparata & Vuillemin (1981) for use as a network topology in parallel computing.

<span class="mw-page-title-main">Cartesian tree</span> Binary tree derived from a sequence of numbers

In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.

A distributed file system for cloud is a file system that allows many clients to have access to data and supports operations on that data. Each data file may be partitioned into several parts called chunks. Each chunk may be stored on different remote machines, facilitating the parallel execution of applications. Typically, data is stored in files in a hierarchical tree, where the nodes represent directories. There are several ways to share files in a distributed architecture: each solution must be suitable for a certain type of application, depending on how complex the application is. Meanwhile, the security of the system must be ensured. Confidentiality, availability and integrity are the main keys for a secure system.

A data center is a pool of resources interconnected using a communication network. A data center network (DCN) holds a pivotal role in a data center, as it interconnects all of the data center resources together. DCNs need to be scalable and efficient to connect tens or even hundreds of thousands of servers to handle the growing demands of cloud computing. Today's data centers are constrained by the interconnection network.

Mary Katherine Vernon is an American computer scientist who works as a professor of computer science and industrial engineering at the University of Wisconsin–Madison. Her research concerns high-performance computer architecture and streaming media.

RIPE Atlas is a global, open, distributed Internet measurement platform, consisting of thousands of measurement devices that measure Internet connectivity in real time.

Timothy M. Pinkston is an American computer engineer, researcher, educator and administrator whose work is focused in the area of computer architecture. He holds the George Pfleger Chair in Electrical and Computer Engineering and is a Professor of Electrical and Computer Engineering at University of Southern California (USC). He also serves in an administrative role as Vice Dean for Faculty Affairs at the USC Viterbi School of Engineering.

<span class="mw-page-title-main">Gabriele Kotsis</span> Austrian university teacher

Gabriele Kotsis is an Austrian computer scientist. She is full professor in computer science at Johannes Kepler University (JKU), Linz, Austria, while leading the Department of Telecommunication and the division of Cooperative Information Systems. She was vice-rector for Research and the Advancement of Women, and longstanding chairwoman of Universities Austria's Policy Committee on Research. She is a distinguished member and elected president of the Association for Computing Machinery (ACM).

Arun K. Somani is Associate Dean for Research of College of Engineering, Distinguished Professor of Electrical and Computer Engineering and Philip and Virginia Sproul Professor at Iowa State University. Somani is Elected Fellow of Institute of Electrical and Electronics Engineers (IEEE) for “contributions to theory and applications of computer networks” from 1999 to 2017 and Life Fellow of IEEE since 2018. He is Distinguished Engineer of Association for Computing Machinery(ACM) and Elected Fellow of The American Association for the Advancement of Science(AAAS).

References

  1. 1 2 Quinn, Michael Jay (2004). Parallel Programming in C with MPI and OpenMP . McGraw-Hill. pp.  31–32. ISBN   978-0-07-282256-4.
  2. 1 2 Lin, M.; Tsang, R.; Du, D.H.C.; Klietz, A.E.; Saroff, S. (1993). "Performance evaluation of the CM-5 interconnection network". Digest of Papers. Compcon Spring, San Francisco, CA, USA, 1993. pp. 189–198. doi:10.1109/CMPCON.1993.289662. ISBN   978-0-8186-3400-0. S2CID   10122972.
  3. Goodman, J.R.; Sequin, C.H. (1981). "Hypertree: A Multiprocessor Interconnection Topology" (PDF). IEEE Transactions on Computers . 20 (12): 923–933. doi:10.1109/TC.1981.1675731. S2CID   20537503.
  4. Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Daniel Hillis, W.; Kuszmaul, Bradley C.; St. Pierre, Margaret A.; Wells, David S.; Wong, Monica C.; Yang, Shaw-Wen; Zak, Robert (1992). "The Network Architecture of the Connection Machine CM-5". SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 272–285. doi:10.1145/140901.141883. ISBN   978-0-89791-483-3. S2CID   6307237.