The standard language for describing the asymptotic behavior of algorithms is theoretical computational complexity. We propose a method for describing the asymptotic behavior of programs in practice by measuring their empirical computational complexity. Our method involves running a program on workloads spanning several orders of magnitude in size, measuring their performance, and fitting these observations to a model that predicts performance as a function of workload size. Comparing these models to the programmer's expectations or to theoretical asymptotic bounds can reveal performance bugs or confirm that a program's performance scales as expected. Grouping and ranking program locations based on these models focuses attention on scalability-critical code. We describe our tool, the Trend Profiler (trend-prof), for constructing models of empirical computational complexity that predict how many times each basic block in a program runs as a linear (y = a + bx) or a powerlaw (y = axb) function of user-specified features of the program's workloads. We ran trend-prof on several large programs and report cases where a program scaled as expected, beat its worst-case theoretical complexity bound, or had a performance bug.

Digital content is for copying: quotation, revision, plagiarism, and file sharing all create copies. Document fingerprinting is concerned with accurately identifying copying, including small partial copies, within large sets of documents.We introduce the class of local document fingerprinting algorithms, which seems to capture an essential property of any finger-printing technique guaranteed to detect copies. We prove a novel lower bound on the performance of any local algorithm. We also develop winnowing, an efficient local fingerprinting algorithm, and show that winnowing's performance is within 33% of the lower bound. Finally, we also give experimental results on Web data, and report experience with MOSS, a widely-used plagiarism detection service.

This paper presents a network mapping algorithm and proves its correctness assuming a traffic-free network.Respecting well-defined parameters, the algorithm produces a graph isomorphic to N -F, where N is the network of switches and hosts and F is the set of switches connected by a switch-bridge to the set of hosts I-I.We show its performance on a Myrinet system-area network with a fat-tree-like topology.It can map 36 nodes, 13 switches and 64 links in 248 ms and 100 nodes, 40 switches, and 193 linksin981 rns.From such maps, the system computes mutually deadlock-free routes and distributes them to all network interfaces.Switched, multi-gigabyte per second, system area networks are the enabling building-blocks for networks of workstations.Because of their core role, these networks should be dynamically recontigurable, automatically adapting to the addition or removal of hosts, switches and links. IntroductionSystem area networks [1] move switched, low-latency, high-speed networks away from the backplanes and cabinets of massively parallel processors into the traditional territory of local area networks.These networks commonly use source-based message routing through anonymous switches.In this regime, their topologies may no longer be the static, well-defined, and well-understood [2] graphs such as hypercubes, meshes.etc., and instead may be arbitrary graphs that change over time.Therefore, systems must periodically discover their topologies rather than assuming one a priori.Lacking an out-of-band mechanism for directly querying switches for their identities, systems must use in-band messaging to disambiguate switch identities when discovering the network topology.From the resulting maps, systems can compute mutually deadlock-free routes without relying upon properties of traditional multicomputer networks, e.g., static topologies, that may now be transient.

We show how an arbitrary strongly-connected directed network of synchronous finite-state automata (with bounded in- and out-degree) can accomplish a number of basic distributed network tasks in O(ND) time (where D is the diameter of the network, N is the number of processors, and the bound on the vertex degree is a constant). These tasks include (among others) the Firing Synchronization Problem; Network Search and Traversal; building outgoing and incoming Spanning Trees; Wake-up and Report When Done; and simulating a step of an undirected network protocol on the underlying graph of the directed network. Preliminary version appeared in the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95) y Bell Communications Research. E-mail: [email protected]. Work done while at University of California at Berkeley Computer Science Division, and International Computer Science Institute at Berkeley and supported by an NSF postdoctoral fellowship and ...

We present nearly tight bounds for wormhole muting on Butterfly networks which indicate it is fundamentally different from store-and-forward packet routing. For instance, consider the problem of routing N log N (randomly generated) log N length messages from the inputs to the outputs of an N input Butterfly. We show that with high probability that this must take time at least /spl Omega/(log/sup 3/N/(log log N)/sup 2/). The best lower bound known earlier was /spl Omega/(log/sup 2/ N), which is simply the flit congestion an each link. Thus our lower bound shows that wormhole routing (unlike store-and-forward-routing) is very ineffective in utilizing communication links. We also give a routing algorithm which nearly matches our lower bound. That is, we show that with high probability the time is O(log/sup 3/ N log log N), which improves upon, the previous best bound of O(log/sup 4/ N). Our method also extends to other networks such as the two-dimensional mesh, where it is nearly optimal. Finally, we consider the problem of offline wormhole routing, where we give optimal algorithms for trees and multidimensional meshes.>