Network security administrators cannot always accurately tell which end-to-end accesses are permitted within their network, and which ones are not. The problem is that every access is determined by the configurations of multiple, separately administered, components. As configurations evolve, a small change in one configuration file can have widespread impact on the end-to-end accesses. Short of exhaustive testing, which is impractical, there are no good solutions to analyze end-to-end flows from network configurations. This paper presents a general technique to analyze all the end-to-end accesses from the configuration files of network routers, switches and firewalls. We efficiently analyze certain state-dependent filter rules. Our goal is to help network security engineers and operators quickly determine configuration errors that may cause unexpected behavior such as unwanted accesses or unreachable services. Our technique can be also be used as part of the change management process, to help prevent network misconfiguration.

This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors; each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random; this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.

We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRN's) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d-1) multiring. 3) Every depth-d multiring /spl Mscr/ can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of /spl Mscr/ resides at a corner of the mesh. 4) Every depth-d HRN /spl Hscr/ can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of /spl Hscr/ resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRN's that are asymptotically tight for large N and d.

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance implementation. Our implementation was guided by the need to keep solutions simple and general. We use a technique for implicitly representing a dynamic global tree across multiple processors which substantially reduces the programming complexity as well as the performance overheads of distributed memory architectures. The contributions include methods to vectorize the computation and minimize communication time which are theoretically and experimentally justified. The code has been tested by varying the number and distribution of bodies on different configurations of the Connection Machine CM-5. The overall performance on instances with 10 million bodies is typically over 48 percent of the peak machine rate, which compares favorably with other approaches.

Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies.

We study the parallel scheduling problem for a new modality of parallel computing: having one workstation "steal cycles" from another. We focus on a draconian mode of cycle-stealing, in which the owner of workstation B allows workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying workstation B with work and receiving its results militates in favor of supplying B with large amounts of work at a time; the risk of losing work in progress when the owner of B reclaims the workstation militates in favor of supplying B with a sequence of small packets of work. The challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stealing. The first attempts to maximize the expected work accomplished during a single episode, when one knows the probability distribution of the return of B's owner. The second attempts to match the productivity of an omniscient cycle-stealer, when one knows how much work that stealer can accomplish. We derive optimal scheduling strategies for sample scenarios within each of these models.

Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

We study a combinatorial problem that is motivated by “client–server” schedulers for parallel computations. Such schedulers are often used, for instance, when computations are being done by a cooperating network of workstations. Our results expose and quantify a control–memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integersk,N> 0, an algorithm that employskFIFO queues in order to schedule anN-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm—which we view as measuring thecontrol complexityof the algorithm—and thememory requirementsof the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integerk∈ {1, 2, ..., log2N}, letQk(N) denote the minimax per-queue capacity for ak-queue algorithm that schedules allN-leaf binary trees; letQ*k(N) denote the analogous quantity forcompletebinary trees. We establish the following bounds: For generalN-leaf binary trees, for allk, [formula]≤Qk(N) ≤ 2N1/k+ 1. For complete binary trees, we derive tighter bounds. We prove that for all constantk, Q*k(N) = Θ[formula]. For generalk, we obtain the following bounds: [formula]≤Q*k(N) ≤ (4k)1−1/k[formula]. Similar trade-offs are readily established for trees of any fixed branching factor.

We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages, we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.

A salvage-embedding (S-embedding) maps an M-leaf complete binary tree into $\mathcal{G}$ an ($N > M$)-leaf complete binary tree $\mathcal{H}$, the fraction G of whose leaves have been labeled GOOD. The S-embedding maps leaves of $\mathcal{G}$ one-to-one to GOOD leaves of $\mathcal{H}$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H\mathop = \limits^{def} M/GN$, and its congestion, the largest number of edges $\mathcal{G}$ that get “routed” across the same edge of $\mathcal{H}$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq \frac{1}{2}$, one can S-embed a $2^{\lfloor {\log ( HGN )} \rfloor }$-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $\log \log N + $ a constant depending only on G and H, no matter how the GOOD leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario—where leaves of $\mathcal{H}$ are labeled GOOD or not, independently, with fixed probability—with probability exceeding $1 - N^{ - \Omega ( 1 )} $, for any target harvest $H \leq 1/8$, one can S-embed a $2^{\lfloor {HN} \rfloor } $-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $O( \log \log \log N )$. In the salvaging scenario, we present an algorithm that, in time $O( CN ( \log N )^{3C + 2} )$, S-embeds in a given a leaf-labeled $\mathcal{H}$ the largest possible $\mathcal{G}$, subject to the prespecified bound C on congestion. This work is inspired by the problem of salvaging a fault-free subnetwork of a leaf-tree machine—a tree architecture whose leaves hold “full-power” processors and whose nonleaf nodes hold “rudimentary” processors that route messages and perform simple combining tasks.

We study a combinatorial problem that is motivated by '(client-server" schedulers for networks of

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance implementation.

Article Free Access Share on An atomic model for message-passing Authors: Pangfeng Liu View Profile , William Aiello View Profile , Sandeep Bhatt View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 154–163https://doi.org/10.1145/165231.165251Published:01 August 1993Publication History 25citation266DownloadsMetricsTotal Citations25Total Downloads266Last 12 Months11Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Many parallel computationsare tree structured; as the computation proceeds, new processes are recursively created while others die out.Algorithms for maintaining dynamically evolving trees on fine-grain parallel architectures must have minimal overhead and must distribute processes evenly among processorsat run-time.A simple randomized strategy for maintaining dynamically evolving binary trees on hypercube networks is presented.The algorithm is distributed and does not require any global information.The algorithm guarantees that every pair of nodes adjacent in the tree are within distance O(loglog N)in an N-processor hypercube.Furthermore, if M is the number of active nodes in the tree at any instant, then, with ovenvhelming probability, no hypercube processors assigned more than 0(1 + (M\N))active nodes.The active nodes in a tree may constitute only leaves of the tree, or all nodes.As a corollary, with high probability, the load is evenly distributed throughout a computation whose running time is polynomial in N, the number of processors.The results can be generalized to bounded-degree trees.Our techniques justify the use of simple algorithms to efficiently parallelize any tree-based computation such as divide-andconquer, backtrack, functional expression evaluation, and to efficiently maintain dynamic data structures such as quad-trees that arise in scientific applications.A novel technique-tree surge~-is introduced to deal with dependencies inherent in trees.Together with tree surgery, the study of random walks is used to analyze the algorithm.

The operations of scattering and gathering in a network of processors involve one processor of the network (P/sub 0/) communicating with all other processors. In scattering, P/sub 0/ sends distinct messages to P/sub 0/. The authors consider networks that are trees of processors. Algorithms for scattering messages from and gathering messages to the processor that resides at the root of the tree are presented. The algorithms are quite general, in that the messages transmitted can differ arbitrarily in length; quite strong, in that they send messages along noncolliding paths, and hence do not require any buffering or queueing mechanisms in the processors; and quite efficient in that algorithms for scattering in general trees are optimal, the algorithm for gathering in a path is optimal and the algorithms for gathering in general trees are nearly optimal. The algorithms can easily be converted using spanning trees to efficient algorithms for scattering and gathering in networks of arbitrary topologies.>

The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded-degree graph with an $O(1)$-separator can be embedded in a hypercube of the same size with dilation and congestion both $O(1)$. It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.

Article Free Access Share on Routing multiple paths in hypercubes Authors: D. Greenberg Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , S. Bhatt Department of Computer Science, Yale University, New Haven, CT and Computer Science Department, 256-80 California Institute of Technology, Pasadena, CA Department of Computer Science, Yale University, New Haven, CT and Computer Science Department, 256-80 California Institute of Technology, Pasadena, CAView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 45–54https://doi.org/10.1145/97444.97457Published:01 May 1990Publication History 12citation363DownloadsMetricsTotal Citations12Total Downloads363Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha < \frac{1}{2}$; $O(n\log n)$ edges if $\alpha = \frac{1}{2}$; $O(n^{2\alpha } )$ edges if $\alpha > \frac{1}{2}$.

A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm.>

Article Free Access Share on Optimal simulations by Butterfly Networks Authors: Sandeep Bhatt Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , Fan Chung Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJView Profile , Jia-Wei Hong Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NYView Profile , Arnold Rosenberg Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 192–204https://doi.org/10.1145/62212.62229Published:01 January 1988Publication History 24citation283DownloadsMetricsTotal Citations24Total Downloads283Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.

Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.

A linear-time approximation algorithm for routing multipoint net channels is presented. The algorithm uses at most a constant factor times the optimal number of tracks required. The notion of channel fluxis introduced and shown, like channel density, to be a lower bound for channel width. Every multipoint net channel having density d and flux f is routed within 2d+O(f) tracks, and every two-point net channel within d+O(f) tracks. Since the flux never exceeds θ(@@@@n), this proves a conjecture of Brown and Rivest [6] that every n-net channel can be routed in O(d+@@@@n) tracks.

Many researchers have proposed that ensembles of processing elements be organized as trees. This paper explores how large tree machines may be assembled efficiently from smaller components. A principal constraint that we consider is the limited number of external connections from an integrated circuit chip. We also explore the emerging capability of restructurable VLSI which allows a chip to be customized after fabrication.