The ability to create and interact with large-scale domain-specific knowledge bases from unstructured/semi-structured data is the foundation for many industry-focused cognitive systems. We will demonstrate the Content Services system that provides cloud services for creating and querying high-quality domain-specific knowledge bases by analyzing and integrating multiple (un/semi)structured content sources. We will showcase an instantiation of the system for a financial domain. We will also demonstrate both cross-lingual natural language queries and programmatic API calls for interacting with this knowledge base.

A basic step in integration is the identification of linkage points, i.e., finding attributes that are shared (or related) between data sources, and that can be used to match records or entities across sources. This is usually performed using a match operator, that associates attributes of one database to another. However, the massive growth in the amount and variety of unstructured and semi-structured data on the Web has created new challenges for this task. Such data sources often do not have a fixed pre-defined schema and contain large numbers of diverse attributes. Furthermore, the end goal is not schema alignment as these schemas may be too heterogeneous (and dynamic) to meaningfully align. Rather, the goal is to align any overlapping data shared by these sources. We will show that even attributes with different meanings (that would not qualify as schema matches) can sometimes be useful in aligning data. The solution we propose in this paper replaces the basic schema-matching step with a more complex instance-based schema analysis and linkage discovery. We present a framework consisting of a library of efficient lexical analyzers and similarity functions, and a set of search algorithms for effective and efficient identification of linkage points over Web data. We experimentally evaluate the effectiveness of our proposed algorithms in real-world integration scenarios in several domains.

Hand-crafted textual patterns have been the mainstay device of practical relation extraction for decades. However, there has been little work on reducing the manual effort involved in the discovery of effective textual patterns for relation extraction. In this paper, we propose a clustering-based approach to facilitate the pattern discovery for relation extraction. Specifically, we define the notion of semantic signature to represent the most salient features of a textual fragment. We then propose a novel clustering algorithm based on semantic signature, S2C, and its enhancement S2C+. Experiments on two real-world data sets show that, when compared with k-means clustering, S2C and S2C+ are at least an order of magnitude faster, while generating high quality clusters that are at least comparable to the best clusters generated by k-means without requiring any manual tuning. Finally, a user study confirms that our clustering-based approach can indeed help users discover effective textual patterns for relation extraction with only a fraction of the manual effort required by the conventional approach.

Information Extraction (IE)-the problem of extracting structured information from unstructured text - has become the key enabler for many enterprise applications such as semantic search, business analytics and regulatory compliance. While rule-based IE systems are widely used in practice due to their well-known "explainability," developing high-quality information extraction rules is known to be a labor-intensive and time-consuming iterative process.

The primary goal of the Midas project is to build a system that enables easy and scalable integration of unstructured and semi-structured information present across multiple data sources. As a first step in this direction, we have built a system that extracts and integrates information from regulatory filings submitted to the U.S. Securities and Exchange Commission (SEC) and the Federal Deposit Insurance Corporation (FDIC). Midas creates a repository of entities, events, and relationships by extracting, conceptualizing, integrating, and aggregating data from unstructured and semi-structured documents. This repository enables applications to use the extracted and integrated data in a variety of ways including mashups with other public data and complex risk analysis.

Currently, WWW , large enterprises, and desktop users suffer from an inability to efficiently access and manage differently structured data. The same data objects (e.g. Product) stored by different databases, repositories, distributed web storage systems, etc are named, referenced, and combined internally into schemas or data structures differently. This leads to structural mismatch of data that often consists of the same semantic objects (e.g. EBay and Yahoo! online auction offers).

We study the problem of extracting flattened tuple data from streaming, hierarchical XML data. Tuple-extraction queries are essentially XML pattern queries with multiple extraction nodes. Their typical applications include mapping-based XML transformation and integrated (set-based) processing of XML and relational data. Holistic twig joins are known for the optimal matching of XML pattern queries on parsed/indexed XML data. Naïve application of the holistic twig joins to streaming XML data incurs unnecessary disk I/Os. We adapt the holistic twig joins for tuple-extraction queries on streaming XML with two novel features: first, we use the block-and-trigger technique to consume streaming XML data in a best-effort fashion without compromising the optimality of holistic matching; second, to reduce peak buffer sizes and overall running times, we apply query-path pruning and existential-match pruning techniques to aggressively filter irrelevant incoming data. We compare our solution with the direct competitor TurboXPath and other alternative approaches that use full-fledged query engines such as XQuery or XSLT engines for tuple extraction. The experiments using real-world XML data and queries demonstrated that our approach 1) outperformed its competitors by up to orders of magnitude, and 2) exhibited almost linear scalability. Our solution has been demonstrated extensively to IBM customers and will be included in customer engagement applications in healthcare.

Schema mappings play a central role in many data integration and data exchange scenarios. In those applications, users need to quickly and correctly specify how data represented in one format is converted into a different format. Clio (L. Popa et al., 2002) is a joint research project between IBM and the University of Toronto studying the creation, maintenance, and use of schema mappings. There have always been two goals in our work in Clio: 1) the automatic creation of logical assertions that capture the way one or more source schemas are mapped into a target schema, and 2) the generation of transformation queries or programs that transform a source data instance into a target data instance.

Clio is an existing schema-mapping tool that provides user-friendly means to manage and facilitate the complex task of transformation and integration of heterogeneous data such as XML over the Web or in XML databases. By means of mappings from source to target schemas, Clio can help users conveniently establish the precise semantics of data transformation and integration. In this paper we study the problem of how to efficiently implement such data transformation (i.e., generating target data from the source data based on schema mappings). We present a three-phase framework for high-performance XML-to-XML transformation based on schema mappings, and discuss methodologies and algorithms for implementing these phases. In particular, we elaborate on novel techniques such as streamed extraction of mapped source values and scalable disk-based merging of overlapping data (including duplicate elimination). We compare our transformation framework with alternative methods such as using XQuery or SQL/XML provided by current commercial databases. The results demonstrate that the three-phase framework (although as simple as it is) is highly scalable and outperforms the alternative methods by orders of magnitude.

Clio, the IBM Research system for expressing declarative schema mappings, has progressed in the past few years from a research prototype into a technology that is behind some of IBM's mapping technology. Clio provides a declarative way of specifying schema mappings between either XML or relational schemas. Mappings are compiled into an abstract query graph representation that captures the transformation semantics of the mappings. The query graph can then be serialized into different query languages, depending on the kind of schemas and systems involved in the mapping. Clio currently produces XQuery, XSLT, SQL, and SQL/XML queries. In this paper, we revisit the architecture and algorithms behind Clio. We then discuss some implementation issues, optimizations needed for scalability, and general lessons learned in the road towards creating an industrial-strength tool.

A new method for fault-tolerant wormhole routing in arbitrary dimensional meshes is introduced. The method was motivated by certain routing requirements of an initial design of the Blue Gene supercomputer at IBM Research. The machine is organized as a three-dimensional mesh containing many thousands of nodes and the routing method should tolerate a few percent of the nodes being faulty. There has been much work on routing methods for meshes that route messages around faults or regions of faults. The new method is to declare certain nonfaulty nodes to be "lambs." A lamb is used for routing but not processing, so a lamb is neither the source nor the destination of a message. The lambs are chosen so that every "survivor node," a node that is neither faulty nor a lamb, can reach every survivor node by at most two rounds of dimension-ordered (such as e-cube) routing. An algorithm for finding a set of lambs is presented. The results of simulations on 2D and 3D meshes of various sizes with various numbers of random node faults are given. For example, on a 32 /spl times/ 32 /spl times/ 32 3D mesh with 3 percent random faults and using at most two rounds of e-cube routing for each message, the average number of lambs is less than 68, which is less than 7 percent of the number 983 of faults and less than 0.21 percent of the number 32,768 of nodes.

Merging and coalescing data from multiple and diverse sources into different data formats continues to be an important problem in modern information systems. Schema matching (the process of matching elements of a source schema with elements of a target schema) and schema mapping (the process of creating a query that maps between two disparate schemas) are at the heart of data integration systems. We demonstrate Clio, a semi-automatic schema mapping tool developed at the IBM Almaden Research Center. In this paper, we showcase Clio's mapping engine which allows mapping to and from relational and XML schemas, and takes advantage of data constraints in order to preserve data associations.

The basis of many systems that integrate data from multiple sources is a set of correspondences between source schemata and a target schema. Correspondences express a relationship between sets of source attributes, possibly from multiple sources, and a set of target attributes. Clio is an integration tool that assists users in defining value correspondences between attributes. In real life scenarios there may be many sources and the source relations may have many attributes. Users can get lost and might miss or be unable to find some correspondences. Also, in many real life schemata the attribute names reveal little or nothing about the semantics of the data values. Only the data values in the attribute columns can convey the semantic meaning of the attribute. Our work relieves users of the problems of too many attributes and meaningless attribute names, by automatically suggesting correspondences between source and target attributes. For each attribute, we analyze the data values and derive a set of features.

The IBM Blue Gene project has endeavored into the development of a cellular architecture computer with millions of concurrent threads of execution. One of the major challenges of this project is demonstrating that applications can successfully exploit this massive amount of parallelism. Starting from the sequential version of a well known molecular dynamics code, we developed a new application that exploits the multiple levels of parallelism in the Blue Gene cellular architecture. We perform both analytical and simulation studies of the behavior of this application when executed on a very large number of threads. As a result, we demonstrate that this class of applications can execute efficiently on a large cellular machine.

Presents parallel algorithms for building decision-tree classifiers on shared-memory multiprocessor (SMP) systems. The proposed algorithms span the gamut of data and task parallelism. The data parallelism is based on attribute scheduling among processors. This basic scheme is extended with task pipelining and dynamic load balancing to yield faster implementations. The task-parallel approach uses dynamic subtree partitioning among processors. Our performance evaluation shows that the construction of a decision-tree classifier can be effectively parallelized on an SMP machine with good speedup.

We consider the problem of broadcasting multiple messages from one processor to many processors in the k-port model for message-passing systems. In such systems, processors communicate in rounds, where in every round, each processor can send k messages to k processors and receive k messages from k processors In this paper, we first present a simple and practical algorithm based on variations of k complete k-ary trees. We then present an optimal algorithm up to an additive term of one for this problem for any number of processors, any number of messages, and any value for k.

This paper studies how to concurrently permute related logical or physical submeshes in a d-dimensional n× … × n physical mesh via wormhole and dimension-ordered routing. Our objective is to minimize the congestion for realizing the permutations, while maximizing the number and dimensionality of permuted submeshes. We show that for d ⩽ 2α + β, concurrent independent permutations of nβ related physical submeshes, each of α dimensions, can be performed in two routing steps without congestion. If the permuted submeshes are logical ones, they can be permuted in one, instead of two, routing step. In addition, any shift operation along any axis of the logical mesh can be performed in the physical mesh without congestion. We also show that if all nodes know the permutation function, any permutation within a submesh of dimensions ⌊2(d − 1)/3⌋ can be realized in three routing steps without congestion.

A partial-sum query obtains the summation over a set of specified cells of a data cube. We establish a connection between the covering problem in the theory of error-correcting codes and the partial-sum problem and use this connection to devise algorithms for the partial-sum problem with efficient space-time trade-offs. For example, using our algorithms, with 44 percent additional storage, the query response time can be improved by about 12 percent; by roughly doubling the storage requirement, the query response time can be improved by about 34 percent.

A partial-sum query obtains the summation over a set of specified cells of a data cube.We establish a connection between the covering problem in the theory of error-correcting codes and the partial-sum problem and use this connection to devise algorithms for the partial-sum problem with efficient space-time trade-offs.For example, using our algorithms, with 44% additional storage, the query response time can be improved by about 12%; by rougbly doubling the storage requirement, the query response time can be improved by about 34%.

A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL.

This paper presents constructions for fault-tolerant, two-dimensional mesh architectures. The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph. They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network. We consider both worst-case and random fault distributions. In terms of worst-case faults, we give a construction that has constant degree and O(k3) spare nodes. This is the first construction known in which the degree is constant and the number of spare nodes is independent of n. In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations) that these constructions can tolerate large numbers of randomly placed faults.

We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k/spl ges/1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time, and on the communication bandwidth.

No abstract available.

Hypercubes, meshes, tori, and Omega networks are well-known interconnection networks for parallel computers. The structure of those graphs can be described in a more general framework called cube graphs. The idea is to assume that every node in a graph with q/sup l/ nodes is represented by a unique string of l symbols over GF(q). The edges are specified by a set of offsets, those are vectors of length l over GF(q), where the two endpoints of an edge are an offset apart. We study techniques for tolerating edge faults in cube graphs that are based on adding redundant edges. The redundant graph has the property that the structure of the original graph can be maintained in the presence of edge faults. Our main contribution is a technique for adding the redundant edges that utilizes constructions of error-correcting codes and generalizes existing ad hoc techniques.

There are a number of models that were proposed in recent years for message passing parallel systems. Examples are the postal model and its generalization the LogP model. In the postal model a parameter /spl lambda/ is used to model the communication latency of the message-passing system. Each node during each round can send a fixed-size message and, simultaneously, receive a message of the same size. Furthermore, a message sent out during round r will incur a latency of /spl lambda/ and will arrive at the receiving node at round r+/spl lambda/-1. Our goal in this paper is to bridge the gap between the theoretical modeling and the practical implementation. In particular, we investigate a number of practical issues related to the design and implementation of two collective communication operations, namely, the broadcast operation and the global combine operation. Those practical issues include, for example, (1) techniques for measurement of the value of /spl lambda/ on a given machine, (2) creating efficient broadcast algorithms that get the latency h and the number of nodes n as parameters and (3) creating efficient global combine algorithms for parallel machines with /spl lambda/ which is not an integer. We propose solutions that address those practical issues and present results of an experimental study of the new algorithms on the Inter Delta machine. Our main conclusion is that the postal model can help in performance prediction and tuning, for example, a properly tuned broadcast improves the known implementation by more than 20%.

Parallel computing on clusters of workstations and personal computers has very high \npotential, since it leverages existing hardware and software. Parallel programming \nenvironments offer the user a convenient way to express parallel computation and communication. \nIn fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial \nstandard for writing "portable" message-passing parallel programs. The communication \npart of MPI consists of the usual point-to-point communication as well as collective \ncommunication. However, existing implementations of programming environments for clusters \nare built on top of a point-to-point communication layer (send and receive) over local \narea networks (LANs) and, as a result, suffer from poor performance in the collective \ncommunication part. \nIn this paper, we present an efficient design and implementation of the collective \ncommunication part in MPI that is optimized for clusters of workstations. Our system consists \nof two main components: the MPI-CCL layer that includes the collective communication \nfunctionality of MPI and a User-level Reliable Transport Protocol (URTP) that interfaces \nwith the LAN Data-link layer and leverages the fact that the LAN is a broadcast medium. \nOur system is integrated with the operating system via an efficient kernel extension \nmechanism that we developed. The kernel extension significantly improves the performance of \nour implementation as it can handle part of the communication overhead without involving \nuser space. \nWe have implemented our system on a collection of IBM RS/6000 workstations con- \nnected via a lOMbit Ethernet LAN. Our performance measurements are taken from typical \nscientific programs that run in a parallel mode by means of the MPI. The hypothesis behind \nour design is that system's performance will be bounded by interactions between the kernel \nand user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our \nresults indicate that the performance of our MPI Broadcast (on top of Ethernet) is about \ntwice as fast as a recently published software implementation of broadcast on top of ATM.

This paper presents a new approach to tolerating edge faults and node faults in (CCC) networks of Cube-Connected Cycles in a worst-case scenario. Our constructions of fault-tolerant CCC networks are obtained by adding extra edges to the CCC. The main objective is to reduce the cost of the fault-tolerant network by minimizing the degree of the network. Specifically, we have two main results. (i) We have created a fault tolerant CCC that can tolerate any single fault, either a node fault or an edge fault. When the dimension of the CCC is odd, the degree of the fault tolerant graph is 4. In the even case, there is a single node per cycle that is of degree 5 and the rest are of degree 4. (ii) We have created a fault-tolerant CCC, where every node has degree y + 2, which can tolerate any 2y − 1 cube-edge faults. Our constructions are extremely efficient for the case of edge faults-they result in healthy CCC networks that utilize all of the processors.

Hypercubes, meshes and tori are well known interconnection networks for parallel computers. The sets of edges in those graphs can be partitioned to dimensions. It is well known that the hypercube can be extended by adding a wildcard dimension resulting in a folded hypercube that has better fault-tolerant and communication capabilities. First we prove that the folded hypercube is optimal in the sense that only a single wildcard dimension ran be added to the hypercube. We then investigate the idea of adding wildcard dimensions to d-dimensional meshes and tori. Using techniques from error correcting codes we construct d-dimensional meshes and tori with wildcard dimensions. Finally, we show how these constructions can be used to tolerate edge and node faults in mesh and torus networks.>

We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately 2 K/3 element transfers in sequence for K elements per node, compared to K element transfers for previously known algorithms. For a binary cube of n=2 dimensions the new algorithm degenerates to yield a complexity of 2 K/+1 element a transfers, which is optimal. The new algorithm is optimal to within a multiplicative factor of 4/3 with respect to the best known 3 lower bound for any routing strategy. We show that the minimum number of element transfers for minimum path length routing is K with concurrent communication on all channels of every node of a binary cube.>

A collective communication library for parallel computers includes frequently used operations such as broadcast, reduce, scatter, gather, concatenate, synchronize, and shift. Such a library provides users with a convenient programming interface, efficient communication operations, and the advantage of portability. A library of this nature, the Collective Communication Library (CCL), intended for the line of scalable parallel computer products by IBM, has been designed. CCL is part of the parallel application programming interface of the recently announced IBM 9076 Scalable POWERparallel System 1 (SP1). In this paper, we examine several issues related to the functionality, correctness, and performance of a portable collective communication library while focusing on three novel aspects in the design and implementation of CCL: 1) the introduction of process groups, 2) the definition of semantics that ensures correctness, and 3) the design of new and tunable algorithms based on a realistic point-to-point communication model.>

Consider a message-passing system of n processors, in which each processor holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n pieces of data and to make the result known to all the n processors. This operation is frequently used in many message-passing systems and is typically referred to as global combine, census computation, or gossiping. This paper explores the problem of global combine in the multiport postal model. This model is characterized by three parameters: n-the number of processors, k-the number of ports per processor, and /spl lambda/-the communication latency. In this model, in every round r, each processor can send k distinct messages to k other processors, and it can receive k messages that were sent from k other processors /spl lambda/-1 rounds earlier. This paper provides an optimal algorithm for the global combine problem that requires the least number of communication rounds and minimizes the time spent by any processor in sending and receiving messages.>

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in O(n/ log/sub 2/ (n+1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of P.K. McKinley and C. Trefftz (1993) requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n /spl les/7.>

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in Theta(n/ log_{2}(n+ 1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of McKinley and Trefftz requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n leqslant 7.

We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully-connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k ≥ 1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time and on the communication bandwidth.

This paper addresses the problem of creating a fault-tolerant interconnection network for a parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m de Bruijn graph, and the shuffle-exchange, are studied. For each topology an N+k node fault-tolerant graph is defined. These fault-tolerant graphs have the property that given any set of k node faults, the remaining N nodes contain the desired topology as a subgraph. All of the constructions given are the best known in terms of the degree of the fault-tolerant graph. We also investigate the use of buses to reduce the degrees of the fault-tolerant graphs still further.>

This paper presents constructions for fault-tolerant two-dimensional mesh architectures.The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph.They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network.We consider both worst-case and random fault distributions.In terms of worst-cme faults, we give a construction that haa constant degree and 0(k3 ) spares.This is the first construction known in which the degree is constant and the number of spares is independent of n.In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations)that they can tolerate large numbers of randomly placed faults.

This paper presents several techniques for tolerating faults in d-dimensional mesh and hypercube architectures. The approach consists of adding spare processors and communication links so that the resulting architecture will contain a fault-free mesh or hypercube in the presence of faults. The authors optimize the cost of the fault-tolerant architecture by adding exactly k spare processors (while tolerating up to k processor and/or link faults) and minimizing the maximum number of links per processor. For example, when the desired architecture is a d-dimensional mesh and k=1, they present a fault-tolerant architecture that has the same maximum degree as the desired architecture (namely, 2d) and has only one spare processor. They also present efficient layouts for fault-tolerant two- and three-dimensional meshes, and show how multiplexers and buses can be used to reduce the degree of fault-tolerant architectures. Finally, they give constructions for fault-tolerant tori, eight-connected meshes, and hexagonal meshes.>

Incomplete hypercubes make the hypercubes more flexible on task allocation in large cubes, cost of manufacturing hardware, and hypercubes with faulty nodes. The authors devise and analyze a broadcasting algorithm based on edge-disjoint spanning trees in an incomplete hypercube of 2/sup n/+2/sup k/ nodes, where 0>

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

Abstract We give practical algorithms, complexity analysis and implementation for one‐to‐all broadcasting, all‐to‐all personalized communication and matrix transpose (with two‐dimensional partitioning of the matrix) on hypercubes. We assume the following communication characteristics: circuit‐switched, e‐cube routing and one‐port communication model. For one‐to‐all broadcasting, we give an algorithm that combines the well‐known recursive doubling algorithm[1] and the algorithm based on edgedisjoint spanning trees[2]. The measured times of the combined algorithm are always superior to those of the edge‐disjoint spanning tree algorithm and outperform the recursive doubling algorithm. For all‐to‐all personalized communication we propose a hybrid algorithm that combines the well‐known recursive doubling algorithm[3,4] and the recently proposed direct‐route algorithm[5,6] Our hybrid algorithm balances between data transfer time and start‐up time of these two algorithms, and its communication complexity is estimated to be better than the two previous algorithms for a range of machine parameters. For matrix transpose with two‐dimensional partitioning of the matrix, we relate a two‐phase algorithm to the previous result in Reference 7. The algorithm is predicted to be better than the recursive transpose algorithm[8] by n nearest‐neighbor communications[4]. It takes advantage of circuit‐switched routing and is congestion‐free within each phase. We also suggest a way of storing the matrix such that the transpose operation can be realized in one phase without congestion.

It is shown that the bisectional interconnection network (BIN) of 2/sup n/ nodes for any even n is isomorphic to the n-dimensional folded hypercube (FHC), an n-dimensional hypercube with additional edges between any two nodes that are of Hamming distance n apart. This observation leads to simplification for the proofs of many interesting properties for the BIN. Inspired by the isomorphism between BIN and FHC, the class of topologies in which nodes are represented by bit strings and two nodes are adjacent if and only if the bitwise Exclusive-OR of their addresses fall in a set of predefined bit string patterns are studied. A few theorems are given to characterize the topology from the mathematical properties of the binary matrix derived from the definition of edges.>

A P(k, d) hyper-pyramid is a level structure of k Boolean cubes where the cube at level i is of dimension id, and a node at level i - 1 connects to every node in a d dimensional Boolean subcube at level i, except for the leaf level k. Hyper-pyramids contain pyramids as proper subgraphs. We show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2d+1/d+2 and from below by 1 + ⌈2d-d/kd+1⌉. For P(k, 2) hyper-pyramids we present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, ⌈log2 n⌉) and expansion 2k⌈log2 n⌉ + 1/nk+1-1/n-1. We also discuss multiple pyramid embeddings.

Four different communication problems are addressed in Boolean n-cube configured multiprocessors: (1) one-to-all broadcasting: distribution of common data from a single source to all other nodes; (2) one-to-all personalized communication: a single node sending unique data to all other nodes; (3) all-to-all broadcasting: distribution of common data from each node to all other nodes; and (4) all-to-all personalized communication: each node sending a unique piece of information to every other node. Three communication graphs (spanning trees) for the Boolean n-cube are proposed for the routing, and scheduling disciplines provably optimum within a small constant factor are proposed. With appropriate scheduling and concurrent communication on all ports of every processor, routings based on these two communication graphs offer a speedup of up to n/2, and O( square root n) over the routings based on the spanning binomial tree for cases (2)-(4) respectively. All three spanning trees offer optimal communication times for cases (2)-(4) and concurrent communication on all ports of every processor. Timing models and complexity analysis are verified by experiments on a Boolean-cube-configured multiprocessor.>