19884866
A Tight Lower Bound on the Size of Visibility Graphs
The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.
9442074
Generalized Latin squares II
Abstract This paper is a continuation of a study on a new class of combinatorial structures called generalized Latin squares or 〈k,l〉-Latin squares. Here, we study the existence question of perfect 〈k,l〉-Latin squares. The main result is an existence theorem for the case M = 2, where M is the multiplicity of the generalized Latin squares. Specifically, we show that for given positive integers N, k = ip, l = iq, where i = gcd(k,l), there exists a perfect 〈k,l〉-Latin square of order N with M = 2 if and only if (i) N = 4k, (ii) pq(p + q)| N, and (iii) q|2.
34776029
Embedding between 2-D meshes of the same size
It is shown how to embed an x/sub 1/ /spl times/ 1/sub 1/ mesh M/sub 1/ into an s/sub 2/ /spl times/ t/sub 2/ mesh M/sub 2/, where s/sub 1/ /spl times/ t/sub 2/, s/sub 1/ < t/sub i/ (i = 1,2) such that the dilation is minimized. It is assumed that load = 1 and expansion = 1. For each case there is shown a lower bound on the dilation and a corresponding embedding method. The dilations by these embedding algorithms either match a lower bound or are very close to a lower bound.<<ETX>>
37059740
Realization of an Arbitrary Permutation on a Hypercube
We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d−3) step realization on a packet-switched d-cube (d⩾3).
33412339
Conservative Algorithms for Parallel and Sequential Integer Sorting
We present a conservative CRCW parallel algorithm for integer sorting. This algorithm sorts n integers from {0, 1, ..., m−1} in time O(n log log min(m,n)/p + log n) using p processors. The simulation of our parallel algorithm on the sequential machine yields a sequential algorithm for integer sorting which sorts n integers from {0, 1, ..., m−1} in time O(n min(log log n, log log m/log n)).
44324303
Equivalent permutation capabilities between time division optical omega network and non-optical extra stage omega network
Since optical networks must support crosstalk-free (CF) connections, regular N/spl times/N multistage interconnection networks (MINs) cannot be directly used to provide connections between N inputs and N outputs. A solution is to use a 2N/spl times/2N Cube-Type MIN to provide the N/spl times/N connections. C. Qiao (1993) proposed a time domain approach that divides the N optical inputs into several groups such that CF connections can be provided by an N/spl times/N regular MIN in several time slots, one for each group. The set of N-permutations realizable in two slots is defined as class /spl theta/. Qiao proved that the size of /spl theta/ is larger than the size of class /spl Omega/, where /spl Omega/ consists of all N-permutations passible through a regular N/spl times/N Omega network. The paper first presents an optimal O(NlgN) time algorithm for identifying whether a given permutation belongs to class /spl theta/ or not. From this algorithm, the paper proves an interesting fact that the class /spl theta/ is identical to the class /spl Omega/+1 which represents the set of N-permutations admissible by a non-optical N/spl times/N one-extra stage Omega network.
16080938
Locality phase prediction
As computer memory hierarchy becomes adaptive, its performance increasingly depends on forecasting the dynamic program locality. This paper presents a method that predicts the locality phases of a program by a combination of locality profiling and run-time prediction. By profiling a training input, it identifies locality phases by sifting through all accesses to all data elements using variable-distance sampling, wavelet filtering, and optimal phase partitioning. It then constructs a phase hierarchy through grammar compression. Finally, it inserts phase markers into the program using binary rewriting. When the instrumented program runs, it uses the first few executions of a phase to predict all its later executions.Compared with existing methods based on program code and execution intervals, locality phase prediction is unique because it uses locality profiles, and it marks phase boundaries in program code. The second half of the paper presents a comprehensive evaluation. It measures the accuracy and the coverage of the new technique and compares it with best known run-time methods. It measures its benefit in adaptive cache resizing and memory remapping. Finally, it compares the automatic analysis with manual phase marking. The results show that locality phase prediction is well suited for identifying large, recurring phases in complex programs.
10424667
Miss Rate Prediction Across Program Inputs and Cache Configurations
Improving cache performance requires understanding cache behavior. However, measuring cache performance for one or two data input sets provides little insight into how cache behavior varies across all data input sets and all cache configurations. This paper uses locality analysis to generate a parameterized model of program cache behavior. Given a cache size and associativity, this model predicts the miss rate for arbitrary data input set sizes. This model also identifies critical data input sizes where cache behavior exhibits marked changes. Experiments show this technique is within 2 percent of the hit rate for set associative caches on a set of floating-point and integer programs using array and pointer-based data structures. Building on the new model, this paper presents an interactive visualization tool that uses a three-dimensional plot to show miss rate changes across program data sizes and cache sizes and its use in evaluating compiler transformations. Other uses of this visualization tool include assisting machine and benchmark-set design. The tool can be accessed on the Web at http://www.cs.rochester.edu/research/locality
16600319
Update-Based Cache Access and Replacement in Wireless Data Access
Cache has been applied for wireless data access with different replacement policies in wireless networks. Most of the current cache replacement schemes are access-based replacement policies since they are based on object access frequency/recency information. Access-based replacement policies either ignore or do not focus on update information. However, update information is extremely important since it can make access information almost useless. In this paper, we consider two fundamental and strongly consistent access algorithms: poll-per-read (PER) and call-back (CB). We propose a server-based PER (SB-PER) cache access mechanism in which the server makes replacement decisions and a client-based CB cache access mechanism in which clients make replacement decisions. Both mechanisms have been designed to be suitable for using both update frequency and access frequency. We further propose two update-based replacement policies, least access-to-update ratio (LA2U) and least access-to-update difference (LAUD). We provide a thorough performance analysis via extensive simulations for evaluating these algorithms in terms of access rate, update rate, cache size, database size, object size, etc. Our study shows that although effective hit ratio is a better metric than cache hit ratio, it is a worse metric than transmission cost, and a higher effective hit ratio does not always mean a lower cost. In addition, the proposed SB-PER mechanism is better than the original PER algorithm in terms of effective hit ratio and cost, and the update-based policies outperform access-based policies in most cases
6253791
Array regrouping and structure splitting using whole-program reference affinity
While the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. This paper defines a model of reference affinity, which measures how close a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, the paper presents k-distance analysis, a practical test for the hierarchical affinity of source-level data. When used for array regrouping and structure splitting, k-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
5990724
Cost-Conscious Cleaning of Massive RFID Data Sets
Efficient and accurate data cleaning is an essential task for the successful deployment of RFID systems. Although important advances have been made in tag detection rates, it is still common to see a large number of lost readings due to radio frequency (RF) interference and tag-reader configurations. Existing cleaning techniques have focused on the development of accurate methods that work well under a wide set of conditions, but have disregarded the very high cost of cleaning in a real application that may have thousands of readers and millions of tags. In this paper, we propose a cleaning framework that takes an RFID data set and a collection of cleaning methods, with associated costs, and induces a cleaning plan that optimizes the overall accuracy-adjusted cleaning costs by determining the conditions under which inexpensive methods are appropriate, and those under which more expensive methods are absolutely necessary.