We present the first parallel architecture for a dynamic approximate membership data-structure (i.e., a filter) that supports insertions, deletions, and approximate membership queries. Our architecture borrows techniques from PRAM emulation to obtain a parallel filter based on two levels of fingerprint-dictionaries. A key component in the architecture is a special-purpose wide-word processor we designed to support operations over small dictionaries. We implemented this architecture on an FPGA running at 100MHz. The implementation stores up to 1.44 million keys, has a false-positive rate less than 0.3%, receives batches 16 of operations per cycle, preserves sequential order, and runs with a stable throughput of over a billion operations per second with respect to several benchmarks.

Abstract We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is $$(f+\varepsilon )$$ ( f + ε ) . Let $$\varDelta $$ Δ denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires $$O(\log {\varDelta } / \log \log \varDelta )$$ O ( log Δ / log log Δ ) rounds, for constants $$\varepsilon \in (0,1]$$ ε ∈ ( 0 , 1 ] and $$f\in {\mathbb {N}}^+$$ f ∈ N + . This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and $$\varepsilon $$ ε , our algorithm improves over the $$(f+\varepsilon )$$ ( f + ε ) -approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is $$O(\log \varDelta + \log W)$$ O ( log Δ + log W ) , where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in $$O(f\log n)$$ O ( f log n ) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of $$O(f\log ^2 n)$$ O ( f log 2 n ) . Finally, for weighted vertex cover ( $$f=2$$ f = 2 ) our algorithm achieves a deterministic running time of $$O(\log n)$$ O ( log n ) , matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an $$(f\lceil \log _2(M)+1 \rceil +\varepsilon )$$ ( f ⌈ log 2 ( M ) + 1 ⌉ + ε ) -approximate integral solution in $$\begin{aligned} O\left( (1+f/\log n)\cdot \left( {\frac{\log \varDelta }{ \log \log \varDelta } + ({f\cdot \log M})^{1.01}\cdot \log \varepsilon ^{-1}\cdot (\log \varDelta )^{0.01}}\right) \right) \end{aligned}$$ O ( 1 + f / log n ) · log

We consider the problem of dynamically assigning n elements unique indices, known as hashcodes, in the range [(1+o(1))n]. This problem is known as perfect hashing and is considered a fundamental building block in the design of more involved data structures. The challenge we address is that of designing a data structure that meets several, seemingly opposing, requirements: (1) the range and the space of the data structure must be, at all times, proportional to the current cardinality nt of the input set, and (2) the hashcodes it assigns must be stable in that the hashcode of an element must not change while the element is continuously in the set. A simple argument shows that these two desiderata are impossible to achieve when arbitrary deletions and insertions are allowed.

Many applications of approximate membership query data structures, or filters , require only an incremental filter that supports insertions but not deletions. However, the design space of incremental filters is missing a "sweet spot" filter that combines space efficiency, fast queries, and fast insertions. Incremental filters, such as the Bloom and blocked Bloom filter, are not space efficient. Dynamic filters (i.e., supporting deletions), such as the cuckoo or vector quotient filter, are space efficient but do not exhibit consistently fast insertions and queries. In this paper, we propose the prefix filter , an incremental filter that addresses the above challenge: (1) its space (in bits) is similar to state-of-the-art dynamic filters; (2) query throughput is high and is comparable to that of the cuckoo filter; and (3) insert throughput is high with overall build times faster than those of the vector quotient filter and cuckoo filter by 1.39X--1.46X and 3.2X--3.5X, respectively. We present a rigorous analysis of the prefix filter that holds also for practical set sizes (i.e., n = 2 25 ). The analysis deals with the probability of failure, false positive rate, and probability that an operation requires accessing more than a single cache line.

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space, and random bits, especially when only a small number of queries are actually issued. Instead, we propose a setting where one generates parts of the sampled graph on-the-fly, in response to queries, and therefore requires amounts of time, space, and random bits that are a function of the actual number of queries. Yet, the responses to the queries correspond to a graph sampled from the distribution in question. Within this framework, we focus on two random graph models: the Barabási-Albert Preferential Attachment model (BA-graphs) ( Science , 286 (5439):509–512) (for the special case of out-degree 1) and the random recursive tree model ( Theory of Probability and Mathematical Statistics , (51):1–28). We give on-the-fly generation algorithms for both models. With probability 1-1/poly( n ), each and every query is answered in polylog( n ) time, and the increase in space and the number of random bits consumed by any single query are both polylog( n ), where n denotes the number of vertices in the graph. Our work thus proposes a new approach for the access to huge graphs sampled from a given distribution, and our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph’s nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their on such graphs.

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank ƒ. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by ƒ. The approximation factor of our algorithm is (ƒ + ε). Let Δ denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log Δ/log log Δ) rounds, for constants ε ∈ (0,1] and ƒ ∈ N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.

In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a collection of groups $\{S_i\}_{i\in[h]}: S_i\subseteq V(G)$. The goal is to find a min-cost subgraph $H$ that connects the root to every group. We consider a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group $S_i$ has a demand $k_i\in[k],k\in\mathbb N$, and we wish to find a min-cost $H\subseteq G$ such that, for each group $S_i$, there is a vertex in $S_i$ connected to the root via $k_i$ (vertex or edge) disjoint paths. While GST admits $O(\log^2 n\log h)$ approximation, its high connectivity variants are Label-Cover hard, and for the vertex-weighted version, the hardness holds even when $k=2$. Previously, positive results were known only for the edge-weighted version when $k=2$ [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint paths may end at different vertices in a group [Chalermsook et al., SODA 2015]. Our main result is an $O(\log n\log h)$ approximation for Restricted Group SNDP that runs in time $n^{f(k, w)}$, where $w$ is the treewidth of $G$. This nearly matches the lower bound when $k$ and $w$ are constant. The key to achieving this result is a non-trivial extension of the framework in [Chalermsook et al., SODA 2017], which embeds all feasible solutions to the problem into a dynamic program (DP) table. However, finding the optimal solution in the DP table remains intractable. We formulate a linear program relaxation for the DP and obtain an approximate solution via randomized rounding. This framework also allows us to systematically construct DP tables for high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth graphs.

We present a new extension of the generalized caching/paging problem that allows the adversary to arbitrarily change the cost or weight of the currently requested page. We present modifications of previous algorithms for generalized caching to handle varying page weights and page costs. In particular, a deterministic algorithm based on~\citeYoung02,CaoIrani97 for an $(h,k)$-competitive algorithm with competitive ratio $k/(k-h+1)$ is presented. In addition, a randomized algorithm based on~\citeBansalBN12,AdamaszekCER12 with competitive ratio $O(łog k)$ is presented. We present three applications that can be supported via reductions to generalized caching with varying page weights and page costs. These applications are: (1)~support of subsets of pages that must be simultaneously present in the cache before entry to a critical section (i.e., working sets), (2)~change of page size due to compression and decompression, (3)~variable cache size (i.e., elastic caches).

This paper presents a deterministic distributed algorithm for computing an f(1+epsilon) approximation of the well-studied minimum set cover problem, for any constant epsilon>0, in O(log (f Delta)/log log (f Delta)) rounds. Here, f denotes the maximum element frequency and Delta denotes the cardinality of the largest set. This f(1+epsilon) approximation almost matches the f-approximation guarantee of standard centralized primal-dual algorithms, which is known to be essentially the best possible approximation for polynomial-time computations. The round complexity almost matches the Omega(log (Delta)/log log (Delta)) lower bound of Kuhn, Moscibroda, Wattenhofer [JACM'16], which holds for even f=2 and for any poly(log Delta) approximation. Our algorithm also gives an alternative way to reproduce the time-optimal 2(1+epsilon)-approximation of vertex cover, with round complexity O(log Delta/log log Delta), as presented by Bar-Yehuda, Censor-Hillel, and Schwartzman [PODC'17] for weighted vertex cover. Our method is quite different and it can be viewed as a locality-optimal way of performing primal-dual for the more general case of set cover. We note that the vertex cover algorithm of Bar-Yehuda et al. does not extend to set cover (when f >= 3).

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space and random bits, especially when only a small number of queries are actually issued. Instead, we propose to generate the graph on-the-fly, in response to queries, and therefore to require amounts of time, space, and random bits which are a function of the actual number of queries. We focus on two random graph models: the Barabási-Albert Preferential Attachment model (BA-graphs) and the random recursive tree model. We give on-the-fly generation algorithms for both models. With probability 1-1/poly(n), each and every query is answered in polylog(n) time, and the increase in space and the number of random bits consumed by any single query are both polylog(n), where n denotes the number of vertices in the graph. Our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph's nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their performance on such graphs.

In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the general graph model. We first describe a general procedure for converting $ε$-testers with a number of rounds $f(D)$, where $D$ denotes the diameter of the graph, to $O((\log n)/ε)+f((\log n)/ε)$ rounds, where $n$ is the number of processors of the network. We then apply this procedure to obtain an optimal tester, in terms of $n$, for testing bipartiteness, whose round complexity is $O(ε^{-1}\log n)$, which improves over the $poly(ε^{-1} \log n)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. In the second part of the paper we design algorithms for testing whether the network is $H$-free for any connected $H$ of size up to four with round complexity of $O(ε^{-1})$. This improves over the $O(ε^{-2})$-round algorithms for testing triangle freeness by Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ by Fraigniaud et al. (DISC 2016). In the last part we generalize the global tester by Iwama and Yoshida (ITCS 2014) of testing $k$-path freeness to testing the exclusion of any tree of order $k$. We then show how to simulate this algorithm in the CONGEST-model in $O(k^{k^2+1}\cdotε^{-k})$ rounds.

We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model (Aiello et al. in SODA, pp 771–780 2003). In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an $$O\left( \log ^{O(1)}(n)\right) $$ competitive ratio for uni-directional grids (where n denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range $$[3 \ldots \log n]$$ . Our randomized algorithm achieves an expected competitive ratio of $$O(\log n)$$ for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous $$O(\log ^2 n)$$ -competitive ratio of Azar and Zachut (ESA, pp 484–495, 2005).

In this paper we improve the approximation ratio for the problem of scheduling packets on line networks with bounded buffers with the aim of maximizing the throughput. Each node in the network has a local buffer of bounded size B, and each edge (or link) can transmit a limited number c of packets in every time unit. The input to the problem consists of a set of packet requests, each defined by a source node, a destination node, and a release time. We denote by n the size of the network. A solution for this problem is a schedule that delivers (some of the) packets to their destinations without violating the capacity constraints of the network (buffers or edges). Our goal is to design an efficient algorithm that computes a schedule that maximizes the number of packets that arrive to their respective destinations. We give a randomized approximation algorithm with constant approximation ratio for the case where the buffer-size to link-capacity ratio, B/c, does not depend on the input size. This improves over the previously best result of O(log^* n) [Räcke and Rosén SPAA 2009]. Our improvement is based on a new combinatorial lemma that we prove, stating, roughly speaking, that if packets are allowed to stay put in buffers only a limited number of time steps, 2d, where d is the longest source-destination distance, then the optimal solution is decreased by only a constant factor. This claim was not previously known in the integral (unsplitable, zero-one) case, and may find additional applications for routing and scheduling algorithms. While we are not able to give the same improvement for the related problem when packets have hard deadlines, our algorithm does support "soft deadlines". That is, if packets have deadlines, we achieve a constant approximation ratio when the produced solution is allowed to miss deadlines by at most log n time units.

A rateless code encodes a finite length information word into an infinitely long codeword such that longer prefixes of the codeword can tolerate a larger fraction of errors. A rateless code achieves capacity for a family of channels if, for every channel in the family, reliable communication is obtained by a prefix of the code whose rate is arbitrarily close to the channel's capacity. As a result, a universal encoder can communicate over all channels in the family while simultaneously achieving optimal communication overhead.

We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link capacities and buffer sizes, and packets may be dropped at any time. The goal of the routing algorithm is to maximize throughput, i.e., route as many packets as possible to their destination. Our main result is an O(log n)-competitive deterministic algorithm for an n-node uni-directional line network (i.e., 1-dimensional grid), requiring only that buffers can store at least 5 packets, and that links can deliver at least 5 packets per step. We note that O(log n) is the best ratio known, even for randomized algorithms, even when allowed large buffers and wide links. The best previous deterministic algorithm for this problem with constant-size buffers and constant-capacity links was O(log5 n)-competitive. Our algorithm works like admission-control algorithms in the sense that if a packet is not dropped immediately upon arrival, then it is "accepted" and guaranteed to be delivered. We also show how to extend our algorithm to a polylog-competitive algorithm for any constant-dimension uni-directional grid.

Message-passing algorithms based on belief-propagation (BP) are successfully used in many applications, including decoding error correcting codes and solving constraint satisfaction and inference problems. The BP-based algorithms operate over graph representations, called factor graphs, that are used to model the input. Although in many cases, the BP-based algorithms exhibit impressive empirical results, not much has been proved when the factor graphs have cycles. This paper deals with packing and covering integer programs in which the constraint matrix is zero-one, the constraint vector is integral, and the variables are subject to box constraints. We study the performance of the min-sum algorithm when applied to the corresponding factor graph models of packing and covering linear programmings (LPs). We compare the solutions computed by the min-sum algorithm for packing and covering problems to the optimal solutions of the corresponding LP relaxations. In particular, we prove that if the LP has an optimal fractional solution, then for each fractional component, the minsum algorithm either computes multiple solutions or the solution oscillates below and above the fraction. This implies that the min-sum algorithm computes the optimal integral solution only if the LP has a unique optimal solution that is integral. The converse is not true in general. For a special case of packing and covering problems, we prove that if the LP has a unique optimal solution that is integral and on the boundary of the box constraints, then the min-sum algorithm computes the optimal solution in pseudopolynomial time. Our results unify and extend recent results for the maximum weight matching problem and for the maximum weight independent set problem.

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora , Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e.g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP decoding fails to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph.

This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length $h$. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability of LP decoding for binary Tanner codes. When the local codes are restricted to single parity-check codes, these bounds also hold for decoding by a certain iterative message-passing decoding algorithm.

Given a channel observation y and a codeword x, we are interested in a one-sided error test that answers the questions: is x optimal with respect to y? is it unique? A positive answer for such a test is called a certificate for the optimality of a codeword. We present new certificates that are based on combinatorial characterization for local-optimality of a codeword in irregular Tanner codes. The certificate is based on weighted normalized trees in computation trees of the Tanner graph. These trees may have any finite height h (even greater than the girth of the Tanner graph). In addition, the degrees of local-code nodes are not restricted to two (i.e., skinny trees). We prove that local-optimality in this new characterization implies ML-optimality and LP-optimality, and show that a certificate can be computed efficiently. We apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP-decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP-decoding fails decays doubly exponentially in the girth of the Tanner graph.

Recent developments in decoding Tanner codes with maximum-likelihood certificates are based on a sufficient condition called local optimality. We define hierarchies of locally optimal codewords with respect to two parameters. One parameter is related to the minimum distance of the local codes in Tanner codes. The second parameter is related to the finite number of iterations used in iterative decoding. We show that these hierarchies satisfy inclusion properties as these parameters are increased. In particular, this implies that a codeword that is decoded with a certificate using an iterative decoder after h iterations is decoded with a certificate after k·h iterations, for every integer k.

We present the first online algorithm with a polylogarithmic competitive ratio for the problem of online routing of packets in unidirectional grids. The goal is to maximize the throughput, i.e., the number of delivered packets. Our online algorithm is deterministic, centralized, handles packets with deadlines, allows bounded buffers, uses adaptive routing, and may drop packets before they reach their destination.

In the generalized connectivity problem, we are given an edge-weighted graph G = ( V , E ) and a collection D = {( S 1 , T 1 ), …, ( S k , T k )} of distinct demands each demand ( S i , T i ) is a pair of disjoint vertex subsets. We say that a subgraph F of G connects a demand ( S i , T i ) when it contains a path with one endpoint in S i and the other in T i . The goal is to identify a minimum weight subgraph that connects all demands in D . Alon et al. (SODA '04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as Steiner forest, facility location with nonmetric costs, tree multicast, and group Steiner tree. Obtaining a nontrivial approximation ratio for generalized connectivity was left as an open problem. We describe the first poly-logarithmic approximation algorithm for generalized connectivity that has a performance guarantee of O (log 2 n log 2 k ). Here, n is the number of vertices in G and k is the number of demands. We also prove that the cut-covering relaxation of this problem has an O (log 3 n log 2 k ) integrality gap. Building upon the results for generalized connectivity, we obtain improved approximation algorithms for two problems that contain generalized connectivity as a special case. For the directed Steiner network problem, we obtain an O ( k 1/2 + ϵ ) approximation which improves on the currently best performance guarantee of Õ ( k 2/3 ) due to Charikar et al. (SODA '98). For the set connector problem, recently introduced by Fukunaga and Nagamochi (IPCO '07), we present a poly-logarithmic approximation; this result improves on the previously known ratio which can be Ω( n ) in the worst case.

We study error bounds for linear programming decoding of regular low-density parity-check (LDPC) codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of σ = 0.735 (upper bound of [(Eb)/(N0)]=2.67 dB) on the threshold of (3, 6)-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.

We study error bounds for linear programming decoding of regular LDPC codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly-exponential in the girth of the factor graph. For memoryless binary-input AWGN channels, we derive lower bounds on the thresholds for regular LDPC codes under LP decoding. Specifically, we prove a lower bound of σ = 0.735 on the threshold of (3, 6)-regular LDPC codes with logarithmic girth.

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = ( V , E ) and an edge set E on V disjoint to E , find a minimum-size subset of edges F ⊆ E such that ( V , E ∪ F ) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.

We present a new micro-architecture for evaluating functions based on piecewise quadratic interpolation. The micro-architecture consists mainly of a look-up table and two multiply-accumulate units. Previous micro-architectures based on piecewise quadratic interpolation have been shown to be efficient for small precision (e.g., single precision) computations. Moreover, they are as fast as piecewise linear interpolation while requiring smaller tables. Our main contribution is in circumventing the need for the additional squaring unit that appears in previous micro-architectures. Based on the proposed micro-architecture, we present a detailed design of single precision reciprocal approximation (1/x). Our design is based on two multiply-accumulate units that contain truncated Booth radix 4 multipliers. The number of partial products in this design is reduced by over 20% compared to previous designs using quadratic interpolation. The latency of this design is roughly the delay of 19 full-adder gates, and it can be easily pipelined into two stages each with a delay of 10 full-adder gates.

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line ( hard capacities ), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution ( soft capacities ). We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item lot-sizing inventory problem with joint set-up costs. For the case of d -dimensional rectangle stabbing with soft capacities, we present a 3 d -approximation algorithm for the unweighted case. For d -dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4 d -approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.

We report the results of an FPGA implementation of double precision floating-point division with IEEE rounding. We achieve a total latency (i.e., cycles times clock period) that is 2:6 times smaller than the latency of the fastest previous implementation on FPGAs. The amount of hardware, on the other hand, is comparable to commercial cores. The division circuit is based on Goldschmidt's algorithm. All IEEE rounding modes are supported and are implemented using dewpoint rounding. The precision of the initial approximation of the reciprocal is 14 bits. To save hardware and reduce the critical path, a half-sized 62x30 Booth radix-8 multiplier is used. This multiplier can receive both the multiplicand and the multiplier in carry-save representation. The division circuit is partitioned into four pipeline stages, has a latency of 11 cycles, and may restart a new double precision division operation after 8 cycles. Synthesis results of an implementation (not including the computation of the initial approximation of the reciprocal and the exponent path) guarantee a clock frequency of 131 MHz on an Altera Stratix II using 3592 ALMs. The implementation was successfully tested with over 10 million random vectors as well as over a million hard-to-round vectors.

Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying positive flow.We prove a hardness result for the Minimum Edge Cost Flow Problem (MECF). Using the one-round two-prover scenario, we prove that MECF does not admit a 2 log 1-ε n -ratio approximation, for every constant ε > 0, unless NP ⊆ DTIME ( n polylogn ).A restricted version of MECF, called Infinite Capacity MECF (ICF), is defined. The ICF problem is defined as follows: (i) all edges have infinite capacity, (ii) there are multiple sources and sinks, where flow can be delivered from every source to every sink, (iii) each source and sink has a supply amount and demand amount, respectively, and (iv) the required total flow is given as part of the input. The goal is to find a minimum edge-cost flow that meets the required total flow while obeying the demands of the sinks and the supplies of the sources. This problem naturally arises in practical scheduling applications, and is equivalent to the special case of single source MECF, with all edges not touching the source or the sink having infinite capacity.The directed ICF generalizes the Covering Steiner Problem in directed and undirected graphs. The undirected version of ICF generalizes several network design problems, such as: Steiner Tree Problem, k -MST, Point-to-point Connection Problem, and the generalized Steiner Tree Problem.An O (log x )-approximation algorithm for undirected ICF is presented. We also present a bi-criteria approximation algorithm for directed ICF. The algorithm for directed ICF finds a flow that delivers half the required flow at a cost that is at most O ( n ε /ε 4 ) times bigger than the cost of an optimal flow. The running time of the algorithm is O ( x 2/ε ċ n 1+1/ε ), where x denotes the required total flow.Randomized approximation algorithms for the Covering Steiner Problem in directed and undirected graphs are presented. The algorithms are based on a randomized reduction to a problem called 1/2-Group Steiner. In undirected graphs, the approximation ratio matches the approximation ratio of Konjevod et al. [2002]. However, our algorithm is much simpler. In directed graphs, the algorithm is the first nontrivial approximation algorithm for the Covering Steiner Problem. Deterministic algorithms are obtained by derandomization.

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA(2) code, compute upper and lower bounds on the word error probability P/sub w/ for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding P/sub w/ demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increases and the channel noise decreases. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound.

We present an IEEE floating-point adder (FP-adder) design. The adder accepts normalized numbers, supports all four IEEE rounding modes, and outputs the correctly normalized rounded sum/difference in the format required by the IEEE Standard. The FP-adder design achieves a low latency by combining various optimization techniques such as: a nonstandard separation into two paths, a simple rounding algorithm, unification of rounding cases for addition and subtraction, sign-magnitude computation of a difference based on one's complement subtraction, compound adders, and fast circuits for approximate counting of leading zeros from borrow-save representation. We present technology-independent analysis and optimization of our implementation based on the Logical Effort hardware model and we determine optimal gate sizes and optimal buffer insertion. We estimate the delay of our optimized design at 30.6 FO4 delays for double precision operands (15.3 FO4 delays per stage between latches). We overview other IEEE FP addition algorithms from the literature and compare these algorithms with our algorithm. We conclude that our algorithm has shorter latency (-13 percent) and cycle time (-22 percent) compared to the next fastest algorithm.

Back in the 60's Goldschmidt presented a variation of Newton-Raphson iterations for division that is well suited for pipelining. The problem in using Goldschmidt's division algorithm is to present an error analysis that enables one to save hardware by using just the right amount of precision for intermediate calculations while still providing correct rounding. Previous implementations relied on combining formal proof methods (that span thousands of lines) with millions of test vectors. These techniques yield correct designs but the analysis is hard to follow and is not quite tight. We present a simple parametric error analysis of Goldschmidt's division algorithm. This analysis sheds more light on the effect of the different parameters on the error. In addition, we derive closed error formulae that allow to determine optimal parameter choices in four practical settings. We apply our analysis to show that a few bits of precision can be saved in the floating-point division (FP-DIV) microarchitecture of the AMD-K7/spl trade/ microprocessor. These reductions in precision apply to the initial approximation and to the lengths of the multiplicands in the multiplier. When translated to cost, the reductions reflect a savings of 10.6% in the overall cost of the FP-DIV microarchitecture.

We propose optimized pipelined implementations for Goldschmidt's division algorithm with IEEE rounding based on Booth radix-8 multiplication. Compared to other FP-division algorithms, our implementations require fewer clock cycles and admit shorter clock periods. The considered optimizations for the quotient approximation are based on a careful general analysis of tight error bounds for the implementation and are accompanied by the utilization of redundant representations, partial compressions, injection-based rounding, and rectangular multipliers for the internal computations. To efficiently achieve IEEE compliant rounding, we introduce the concept of dew-point rounding that allows efficient implementation and reduced requirements for the quotient approximation. On this basis, we propose the implementation of different versions of Goldschmidt's division algorithm with different pipeline depths. None of these implementations requires a full-sized multiplier at any stage of the computations. In this way we reduce latency, cost, and enable increased throughput at a reasonable cost. We suggest a full range of pipelining depths: On one extreme is a 3-stage pipeline with a restart time that simply equals the latency minus the number of pipeline stages. On the other extreme is a fully pipelined design.

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system $(X,{\cal S})$, where each $S \in {\cal S}$ is a subset of X. The output is a coloring $\chi$ of the sets in ${\cal S}$ that satisfies the following constraint: for every $x \in X$ there exists a color i and a unique set $S \in {\cal S}$ such that $x \in S$ and $\chi(S) = i$. The goal is to minimize the number of colors used by the coloring $\chi$. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, $\Theta(\log n)$ colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system $(X,{\cal S})$, the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set $S \in {\cal S}$ contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version.

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem called minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S /spl isin/ S is a subset of X. The output is a coloring X of the sets in S that satisfies the following constraint: for every x /spl isin/ X there exists a color i and a unique set S /spl isin/ S, such that x /spl isin/ S and /spl chi/(S) = i. The goal is to minimize the number of colors used by the coloring X. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and non-congruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle) regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally-symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). For rectangles and hexagons we obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also show that, even in the case of unit disks, /spl Theta/(log n) colors may be necessary.

We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing on the plane of a bounded degree graph; and (ii) minimizing the VLSI layout area of a graph of maximum degree four. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log 3 n )$ times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a graph of maximum degree four in a square grid whose area is O(log 4 n )$ times the minimum layout area. This is an O(log 2 n ) improvement over the best known long-standing result.

We present an IEEE floating-point adder (FP-adder) design. The adder accepts normalized numbers, supports all four IEEE rounding modes, and outputs the correctly normalized rounded sum/difference in the format required by the IEEE standard. The latency of the design for double precision is roughly 24 logic levels, not including delays of latches between pipeline stages. Moreover, the design can be easily partitioned into 2 stages consisting of 12 logic levels each, and hence, can be used with clock periods that allow for 12 logic levels between latches. The FP-adder design achieves low latency by combining various optimization techniques such as: a non-standard separation into two paths, a simple rounding algorithm, unifying rounding cases for addition and subtraction, sign-magnitude computation of a difference based on complement subtraction, compound adders, and fast circuits for approximate counting of leading zeros from borrow-save representation. A comparison of our design with other implementations suggests a reduction in the latency by at least two logic levels as well as simplified rounding implementation. A reduced precision version of our algorithm has been verified by exhaustive testing.

Article Free Access Share on Improved approximations of crossings in graph drawings Authors: Guy Even Dept. of Electrical Engineering, Tel Aviv University, Tel Aviv 69978, Israel Dept. of Electrical Engineering, Tel Aviv University, Tel Aviv 69978, IsraelView Profile , Sudipto Guha Computer Science Department, Stanford University, Standord, CA Computer Science Department, Stanford University, Standord, CAView Profile , Baruch Schieber IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 296–305https://doi.org/10.1145/335305.335340Published:01 May 2000Publication History 12citation325DownloadsMetricsTotal Citations12Total Downloads325Last 12 Months9Last 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

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, τ, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is O (min{log τ, log log τ, log k log log k }) where k denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices. We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d -dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and p -separators (for small values of p ) in directed graphs.

A technique for automatically producing a rectilinear planar drawings of interconnection networks is described. It is based on the layered cross product suggested by Even and Litman. The technique is demonstrated on the butterfly network, the binary tree, and the mesh-of-trees of Leighton. © 2000 John Wiley & Sons, Inc.

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G=(V,E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow.

Let G=(V,E) be a weighted undirected graph where all weights are at least one. We consider the following generalization of feedback set problems. Let $S \subset V$ be a subset of the vertices. A cycle is called interesting if it intersects the set S. A subset feedback edge (vertex) set is a subset of the edges (vertices) that intersects all interesting cycles. In minimum subset feedback problems the goal is to find such sets of minimum weight. This problem has a variety of applications, among them genetic linkage analysis and circuit testing. The case in which S consists of a single vertex is equivalent to the multiway cut problem, in which the goal is to separate a given set of terminals. Hence, the subset feedback problem is NP-complete and also generalizes the multiway cut problem. We provide a polynomial time algorithm for approximating the subset feedback edge set problem that achieves an approximation factor of two. This implies a $\Delta$-approximation algorithm for the subset feedback vertex set problem, where $\Delta$ is the maximum degree in G. We also consider the multicut problem and show how to achieve an $O(\log \tau^*)$ approximation factor for this problem, where $\tau^*$ is the value of the optimal fractional solution. To achieve the $O(\log \tau^*)$ factor we employ a bootstrapping technique.

Engineering design methodology recommends designing a system as follows: Start with an unambiguous specification, partition the system into blocks, specify the functionality of each block, design each block separately, and glue the blocks together. Verifying the correctness of an implementation then reduces to a local verification procedure. We apply this methodology for designing a provably correct IEEE rounding unit that can be used for various operations, such as addition and multiplication. First, we provide a mathematical and, hopefully, unambiguous definition of the IEEE Standard which specifies the functionality. We give explicit and concise rules for gluing the rounding unit with a floating-point adder and multiplier. We then present floating-point addition and multiplication algorithms that use the rounding unit. To the best of our knowledge, our design is the first publication that deals with detecting exceptions and trapped overflow and underflow exceptions as an integral part of the rounding unit in a floating point unit. Our abstraction level avoids bit-level representations and arguments to help clarify the functionality of the algorithm.

A new IEEE compliant floating-point rounding algorithm for computing the rounded product from a carry-save representation of the product is presented. The new rounding algorithm is compared with the rounding algorithms of Yu and Zyner (1995) and of Quach et al. (1991). For each rounding algorithm, a logical description and a block diagram is given, the correctness is proven, and the latency is analyzed. We conclude that the new rounding algorithm is the fastest rounding algorithm, provided that an injection (which depends only on the rounding mode and the sign) can be added in during the reduction of the partial products into a carry-save encoded digit string. In double precision format, the latency of the new rounding algorithm is 12 logic levels compared to 14 logic levels in the algorithm of Quach et al. and 16 logic levels in the algorithm of Yu and Zyner.

This paper presents a floating-point addition algorithm and adder pipeline design employing a packet forwarding pipeline paradigm. The packet forwarding format and the proposed algorithms constitute a new paradigm for handling data hazards in deeply pipelined floating-point pipelines. The addition and rounding algorithms employ a four stage execution phase pipeline with each stage suitable for implementation in a short clock period, assuming about 15 logic levels per cycle. The first two cycles are related to addition proper and are the focus of this paper. The last two cycles perform the rounding and have been covered in a paper by D.W. Matula and A.M. Nielsen (1997). The addition algorithm accepts one operand in a standard binary floating-point formal at the start of cycle one. The second operand is represented in the packet forwarding floating-point format: namely, it is divided into four parts: the sign bit, the exponent string, the principal part of the significant, and the carry-round packet. The first three parts of the second operand are input at the start of cycle one and the carry-round packet is input at the start of cycle two. The result is output in two formats that both represent the rounded result as required by the IEEE 754 standard. The result is output in the packet forwarding floating-point format at the end of cycles two and three to allow forwarding with an effective latency of two cycles. The result is also format at the end of cycle four for retirement to a register. The packet forwarding result is thus available with an effective two cycle latency for forwarding to the start of the adder pipeline or to a cooperating multiplier pipeline accepting a packet forwarding operand. The effective latency of the proposed design is two cycles for successive dependent operations while perceiving IEEE 754 binary floating-point compatibility.

A novel IEEE compliant floating point rounding algorithm for computing the rounded product from a carry-save representation of the product is presented. The new rounding algorithm is compared with the rounding algorithms of R. Yu and G. Zyner (1995) and of N. Quach et al. (1991). For each rounding algorithm, a logical description and a block diagram is given and the latency is analyzed. We conclude that the new rounding algorithm is the fastest rounding algorithm, provided that an injection (which depends only on the rounding mode and the sign) can be added in during the reduction of the partial products into a carry-save encoded digit string. In double precision the latency of the new rounding algorithm is 12 logic levels compared to 14 logic levels in the algorithm of Quach et al., and 16 logic levels in the algorithm of Yu and Zyner.

We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity $\rho$-separators. A $\rho$-separator is a subset of edges whose removal partitions the vertex set into connected components such that the sum of the vertex weights in each component is at most $\rho$ times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity $\rho$-separators which is based on spreading metrics yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-balanced partitions. In particular, this result improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhancethese results by presenting a version of the algorithm that obtains an O(log OPT)-approximation factor. The algorithm is based on a technique called spreading metrics that enables us to formulate directly the minimum capacity $\rho$-separator problem as an integer program. We also introduce a generalization called the simultaneous separator problem, where the goal is to find a minimum capacity subset of edges that separates a given collection of subsets simultaneously. We extend our results to directed graphs for values of $\rho \geq 1/2$. We conclude with an efficient algorithm for computing an optimal spreading metric for $\rho$-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.

We present an algorithm for IEEE floating-point addition. The latency of the addition algorithm for double precision is roughly 24 logic levels, not including delays of latches between pipeline stages. The algorithm accepts normalized numbers, supports all four IEEE rounding modes, and outputs the correctly rounded sum/difference in the format required by the IEEE Standard. The presentation of the algorithm is technology independent and can serve as basis for evaluation and comparison with other floating-point addition algorithms.

Engineering design methodology recommends designing a system as follows: start with an unambiguous specification, partition the system into blocks, specify the functionality of each block, design each block separately, and glue the blocks together. Verifying the correctness of an implementation then reduces to a local verification procedure. We apply this methodology for designing a provably correct, modular, IEEE-compliant floating point unit. First, we provide a mathematical, and hopefully unambiguous, definition of IEEE Standard 754 (1985) which specifies the functionality. The design consists of an adder, a multiplier and a rounding unit, each of which is further partitioned. Our floating point unit design deals with the detection of exceptions and trapped overflow and underflow exceptions as an integral part of the rounding unit. Our abstraction level avoids bit-level arguments while still enabling the addressing of crucial implementation issues such as delay and cost.

For pt.I see ibid., p.140-7 (1997). The paper presents a floating point addition algorithm and adder pipeline design employing a packet forwarding pipeline paradigm. The packet forwarding format and the proposed algorithms constitute a new paradigm for handling data hazards in deeply pipelined floating point pipelines. The addition algorithm employs a four stage execution phase pipeline with each stage suitable for implementation in a short clock period, assuming about fifteen logic levels per cycle. The first two cycles are related to addition proper and are the principal focus of the paper. The last two cycles perform the rounding. The addition algorithm accepts one operand in a standard binary floating point format at the start of cycle one. Packets comprising the other operand in our packet forwarding floating point format are input at the start of cycles one and two. Output of the result occurs in the packet format after cycles two and three with the format representing a floating point value equal to the standard IEEE 754 rounded result. The same result in a standard binary floating point format is available after cycle four for retirement to a register. The packet forwarding result is thus available with an effective two cycle latency for forwarding to the start of the adder pipeline or to a cooperating multiplier pipeline accepting a packet forwarding operand. The effective latency of the proposed design is two cycles for successive dependent operations while preserving IEEE 754 binary floating point compatibility.

In general, mapping a circuit onto several chips incurs a physical setting which differs from those within a chip. Specifically, the delay of chip-to-chip interconnections is much longer than on-chip delays of wires and gates. This delay effects the bandwidth as well. In addition, the clock skew between chips is larger than the clock skew within a chip. One may mistakenly conclude that the feasible clock period of a systolic array cannot be smaller than the maximal delay of an interconnection in a realization of the circuit. This paper proposes a technique for mapping large systolic linear arrays and systolic two-dimensional arrays onto several chips while almost maintaining the clock rates which are obtainable when these circuits are small enough to fit into a single chip. Our solution does not rely on special analogue techniques. It is described in a sequence of transformations (logic duplication and retiming), reductions, and an implementation of interconnections which have a required behavior in a given physical setting. It is shown that each step preserves functionality, and subsequently, the correctness of the proposed solution is implied.

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set. The input in this problem consists of an undirected graph G=(V,E) with vertex weights w(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset feedback vertex set with respect to S if it intersects every interesting cycle The goal is to find a minimum weight subset feedback vertex set. The best pervious algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset feedback vertex set problem generalizes two NP-Complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multi-commodity flow which we call relaxed multi-commodity flow. Relaxed multi-commodity flow is a hybrid of multi-commodity flow and multi-terminal flow.

Retiming is a very promising transformation of circuits which preserves functionality and improves performance. Its benefits are especially promising in automatic synthesis of circuits from higher-level descriptions. However, retiming has not been widely included in current design tools and methodologies. One of the main obstacles is the problem of finding an equivalent initial state for the retimed circuit. In this paper, we introduce a simple modification of the retiming algorithm of Leiserson and Saxe. The modified algorithm helps minimize the effort required to find equivalent initial states and reduces the chance that the network needs to be modified in order to find an equivalent initial state. This algorithm is the kernel of a new efficient retiming method, which searches for optimal retimings while preserving the initial state condition. The paper also presents an improved method to perform the initial state calculation.

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimisation problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound, /spl tau/, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modelled by our paradigm whose approximation factor is O (mi.

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.