Distributed graph processing frameworks formulate tasks as sequences of supersteps within which communication is performed asynchronously by sending messages over the graph edges. PageRank’s communication pattern is identical across all its supersteps since each vertex sends messages to all its edges. We exploit this pattern to develop a new communication paradigm that allows us to exchange messages that include only edge payloads, dramatically reducing bandwidth requirements. Experiments on a web graph of 38 billion vertices and 3.1 trillion edges yield execution times of 34.4 seconds per iteration, suggesting more than an order of magnitude improvement over the state-of-the-art.

Connected Components is a fundamental graph mining problem that has been studied for the PRAM, MapReduce and BSP models. We present a simple CC algorithm for BSP that does not mutate the graph, converges in O(log n) supersteps and scales to graphs of trillions of edges.

Word2Vec recently popularized dense vector word representations as fixed-length features for machine learning algorithms and is in widespread use today. In this paper we investigate one of its core components, Negative Sampling, and propose efficient distributed algorithms that allow us to scale to vocabulary sizes of more than 1 billion unique words and corpus sizes of more than 1 trillion words.

The classic Set Cover problem requires selecting a minimum size subset A ⊆ F from a family of finite subsets F Of U such that the elements covered by A are the ones covered by F. It naturally occurs in many settings in web search, web mining and web advertising. The greedy algorithm that iteratively selects a set in F that covers the most uncovered elements, yields an optimum (1+ln |U|)-approximation but is inherently sequential. In this work we give the first MapReduce Set Cover algorithm that scales to problem sizes of ∼ 1 trillion elements and runs in logp Δ iterations for a nearly optimum approximation ratio of p ln Δ, where Δ is the cardinality of the largest set in F

In this work we advocate the adoption of Binary Decision Diagrams (BDDs) for storing and manipulating Time-Series datasets. We first propose a generic BDD transformation which identifies and removes 50% of all BDD edges without any loss of information. Following, we optimize the core operation for adding samples to a dataset and characterize its complexity. We identify time-range queries as one of the core operations executed on time-series datasets, and describe explicit Boolean function constructions that aid in efficiently executing them directly on BDDs. We exhibit significant space and performance gains when applying our algorithms on synthetic and real-life biosensor time-series datasets collected from field trials.

Ordered Binary Decision Diagrams are a canonical representation of Boolean functions that is at the core of most formal verification systems and silicon compilers. Canonicity enables efficiency of manipulation but comes at the cost of fixing a variable evaluation order and predictably, BDD sizes are very sensitive to the selected order. The state-of-the-art reordering algorithms are based on transpositions of consecutive variables (swaps). Exact algorithms enumerate all possible n! permutations by performing a series of at least n! -- 1 swaps, while heuristics typically either search for the optimum location of each variable independently (sifting) or utilize exact algorithms as a subroutine (k-window.) In this work we reduce the problem of variable ordering to that of obtaining a permutation enumeration transposition network. Our proposed network avoids traversing all n! permutations by exploiting structural properties of BDDs and requires the execution of fewer than 4n swaps sequentially instead of n! -- 1. For the practically interesting cases of n = 4,5 our algorithm requires only 11 (resp 59) sequential swaps instead of 23 (resp 119). We also propose an algorithm for moving between arbitrary variable orderings that executes at most n swaps sequentially, an improvement upon (n2). Results suggest speedups of 162%, 308%, > 10X over the k -- window heuristic for k = 4, 6,8 and near-linear speedups when moving between orderings.

We present the architecture of a new Ordered Binary Decision Diagram library that is designed from the ground up to be space efficient. The main novelty lies in the library's node structure, which is modified at run-time to closely follow the variations in size of the stored OBDDs. We compare the new library with existing OBDD libraries on ACM/SIGDA and industrial circuits and report significant performance and space gains.

With technology scaling, the wire delay as a fraction of the total delay is increasing, and the communication architecture is becoming a major bottleneck for system performance in systems on chip (SoCs). A communication-centric design paradigm, networks on chip (NoCs), has been proposed recently to address the communication issues of SoCs. As the geometries of devices approach the physical limits of operation, NoCs will be susceptible to various noise sources such as crosstalk, coupling noise, process variations, etc. Designing systems under such uncertain conditions become a challenge, as it is harder to predict the timing behavior of the system. The use of conservative design methodologies that consider all possible delay variations due to the noise sources, targeting safe system operation under all conditions will result in poor system performance. An aggressive design approach that provides resilience against such timing errors is required for maximizing system performance. In this paper, we present T-error, which is a timing-error-tolerant aggressive design method to design the individual components of the NoC (such as switches, links, and network interfaces), so that the communication subsystem can be clocked at a much higher frequency than a traditional conservative design (up to 1.5x increase in frequency). The NoC is designed to tolerate timing errors that arise from overclocking without substantially affecting the latency for communication. We also present a way to dynamically configure the NoC between the overclocked mode and the normal mode, where the frequency of operation is lower than or equal to the traditional design's frequency, so that the error recovery penalty is completely hidden under normal operation. Experiments on several benchmark applications show large performance improvement (up to 33% reduction in average packet latency) for the proposed system when compared to traditional systems.

The limited scalability of current bus topologies for systems on chips (SoCs) dictates the adoption of networks on chips (NoCs) as a scalable interconnection scheme. Current SoCs are highly heterogeneous in nature, denoting homogeneous, preconfigured NoCs as inefficient drop-in alternatives. While highly parametric, fully synthesizeable (soft) NoC building blocks appear as a good match for heterogeneous MPSoC architectures, the impact of instantiation-time flexibility on performance, power and silicon cost has not yet been quantified. The paper details /spl times/pipes Lite, a design flow for automatic generation of heterogeneous NoCs. /spl times/pipes Lite is based on highly customizable, high frequency and low latency NoC modules, that are fully synthesizeable. Synthesis results provide modules that are directly comparable, if not better, than the current published state-of-the-art NoCs in terms of area, power latency and target operating frequency measurements.

The growing complexity of customizable single-chip multiprocessors is requiring communication resources that can only be provided by a highly-scalable communication infrastructure. This trend is exemplified by the growing number of network-on-chip (NoC) architectures that have been proposed recently for system-on-chip (SoC) integration. Developing NoC-based systems tailored to a particular application domain is crucial for achieving high-performance, energy-efficient customized solutions. The effectiveness of this approach largely depends on the availability of an ad hoc design methodology that, starting from a high-level application specification, derives an optimized NoC configuration with respect to different design objectives and instantiates the selected application specific on-chip micronetwork. Automatic execution of these design steps is highly desirable to increase SoC design productivity. This work illustrates a complete synthesis flow, called Netchip, for customized NoC architectures, that partitions the development work into major steps (topology mapping, selection, and generation) and provides proper tools for their automatic execution (SUNMAP, xpipescompiler). The entire flow leverages the flexibility of a fully reusable and scalable network components library called xpipes, consisting of highly-parameterizable network building blocks (network interface, switches, switch-to-switch links) that are design-time tunable and composable to achieve arbitrary topologies and customized domain-specific NoC architectures. Several experimental case studies are presented In the work, showing the powerful design space exploration capabilities of the proposed methodology and tools.

This work presents theoretical results and an efficient heuristic algorithm for minimizing single - output exclusive - or sum-of-products expressions, based on an iterative product term transformation paradigm. Experimental results verify the efficiency of the algorithm in terms of execution times and product term count of the produced expression, when compared to a state-of-the-art heuristic ESOP minimizer for single-output benchmark and randomly generated functions.

The adoption of hardware description languages as a design specification formalism, in the electronic design automation industry, has reached acceptance during the last years. This effort has been mainly supported by the VHDL and Verilog standardization activities, which are now offering a common formalism among different tool vendors, as well as novel ideas like the SystemCC++ class library, which promises hardware modeling using C++ syntax and a higher level of specification abstraction. The broad range of modern description language spectrum, supports efficient language based synthesis processes, starting at even higher abstraction levels. This paper presents a language based design environment, which combines synthesis and formal verification tasks, using an advanced compiler generator and based on language transformations. This combination, presenting low complexity, offers more power to language based synthesis and design management and can be used to find errors and better understand issues of behavioral modeling.