Now showing items 171-190 of 245

    • RCMP: A System Enabling Efficient Re-computation Based Failure Resilience for Big Data Analytics 

      Dinu, Florin; Ng, T. S. Eugene (2013-04-30)
      Multi-job I/O-intensive big-data computations can suffer a significant performance hit due to relying on data replication as the main failure resilience strategy. Data replication is inherently an expensive operation for I/O-intensive jobs because the datasets to be replicated are very large. Moreover, since the failure resilience guarantees provided ...
    • Reasoning About Multi-Stage Programs 

      Inoue, Jun; Taha, Walid (2011-10-15)
      We settle three basic questions that naturally arise when verifying multi-stage functional programs. Firstly, does adding staging to a language compromise any equalities that hold in the base language? Unfortunately it does, and more care is needed to reason about terms with free variables. Secondly, staging annotations, as the name “annotations” ...
    • Reasoning About Staged Programs 

      Inoue, Jun; Taha, Walid (2009-07-14)
      Multi-stage programming (MSP) is a style of writing program generators---programs which generate programs---supported by special annotations that direct construction, combination, and execution of object programs. Various researchers have shown MSP to be effective in writing efficient programs without sacrificing genericity. However, correctness ...
    • Reducing the Impact of Spill Code 

      Harvey, Timothy J. (1998-07-24)
      All graph-coloring register allocators rely on heuristics to arrive at a "good" answer to the NP-complete problem of register allocation, resulting in suboptimal code due to spill code. We look at a post-pass to the allocator that removes unnecessary spill code by finding places where the availability of an unused register allows us to "promote a ...
    • Register Allocation using Bipartite Liveness Graphs 

      Barik, Rajkishore; Sarkar, Vivek; Zhao, Jisheng (2010-10-12)
      Register allocation is an essential optimization for all compilers. A number of sophisticated register allocation algorithms have been developed based on Graph Coloring (GC) over the years. However, these algorithms pose three major limitations in practice. First, construction of a full interference graph can be a major source of space and time ...
    • Register Allocation via Graph Coloring 

      Briggs, Preston (1992-04)
      Chaitin and his colleagues at IBM in Yorktown Heights built the first global register allocator based on graph coloring. This thesis describes a series of improvements and extensions to the Yorktown allocator. There are four primary results: Optimistic coloring—Chaitin's coloring heuristic pessimistically assumes any node of high degree will not be ...
    • Relating Linear and Branching Model Checking 

      Kupferman, Orna; Vardi, Moshe Y. (1998-06-08)
      The difference in the complexity of branching and linear model checking has been viewed as an argument in favor of the branching paradigm. In particular, the computational advantage of CTL model checking over LTL model checking makes CTL a popular choice, leading to efficient model-checking tools for this logic. Can we use these tools in order to ...
    • Resource Constrained Loop Fusion 

      Ding, Chen; Kennedy, Ken (2003-09-03)
      Embedded processors have limited on-chip memory. Fusing loops that use the same data can reduce the distance between accesses to the same memory location, avoiding costly off-chip memory transfer. Most existing greedy fusion algorithms solve the unconstrained problem—they do not guard against negative effects of excessive fusion. When a large program ...
    • Robotics-Based Location Sensing based on Wireless Ethernet 

      Bekris, Kostas E.; Kavraki, Lydia E.; Ladd, Andrew M.; Marceau, Guillaume; Rudys, Algis; (2002-04-25)
      A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position from measured RF signal strengths in the IEEE 802.11b wireless Ethernet network. Previous approaches in the location-aware field with ...
    • Routing Improvements using Directional Antennas in Mobile Ad hoc Networks 

      Johnson, David B.; Saha, Amit (2003-07-03)
      In this paper, we present the design and evaluation of two techniques for routing improvement using directional antennas in mobile ad-hoc networks. First, we use directional antennas to bridge network partitions by adaptively transmitting selected packets over a longer distance, using the capabilities of the directional antenna, yet still transmitting ...
    • Runtime Support for Distributed Sharing in Strongly-Typed Languages 

      Cox, Alan L.; Hu, Y. Charlie; Wallach, Dan S.; Yu, Weimin; Zwaenepoel, Willy (1999-11-13)
      In this paper, we present a new run-time system for strongly-typed programming languages that supports object sharing in a distributed system. The key insight in this system is that type information allows efficient and transparent sharing of data with both fine-grained and coarse-grained access patterns. In contrast, conventional distributed shared ...
    • Saddle points in random matrices: analysis of Knuth search algorithms 

      Hofri, Micha; Jacquet, Philippe (1997-12-22)
      In this note we present an analysis of algorithms for finding saddle points in a random matrix, presented by Donald E. Knuth as exercise 1.3.2-12 in The Art of Computer Programming. We estimate the average computing costs of three saddle point search algorithms. Amusingly, the asymptotic results in this analysis about matrix saddle points uses the ...
    • Scalability and Data Placement on SGI Origin 

      Chauhan, Arun; Ding, Chen; Sheraw, Berry (1998-04-01)
      Cache-coherent non-uniform memory access (ccNUMA) architectures have attracted lots of academic and industry interests as a promising direction to large scale parallel computing. Data placement has been used as a major optimization method on such machines. This study examined the scalability and the effect of data placement on a state-of-the-art ...
    • Scalable and Precise Dynamic Datarace Detection for Structured Parallelism 

      Raman, Raghavan; Zhao, Jisheng; Sarkar, Vivek; Vechev, Martin; Yahav , Eran (2012-07-06)
      Existing dynamic race detectors suffer from at least one of the following three limitations: i) space overhead per memory location grows linearly with the number of parallel threads [13], severely limiting the parallelism that the algorithm can handle. (ii) sequentialization: the parallel program must be processed in a sequential order, usually ...
    • Scalable Grid Application Scheduling via Decoupled Resource Selection and Scheduling 

      Casanova, Henri; Chien, Andrew A.; Kee, Yang-Suk; Kennedy, Ken; Koelbel, Charles; (2006-01-20)
      Over the past years grid infrastructures have been deployed at larger and larger scales, with envisioned deployments incorporating tens of thousands of resources. Therefore, application scheduling algorithms can become unscalable (albeit polynomial) and thus unusable in large-scale environments. One reason for unscalability is that these algorithms ...
    • Scalarizing Fortran 90 Array Syntax 

      Kennedy, Ken; Zhao, Yuan (2001-03-30)
      Array syntax is an important feature introduced in Fortran 90. It adds more expressive power to the language by allowing operations and assignments on the array sections. Programmers will benefit from this new feature directly by writing simple and concise programs. The remaining work is left to compilers that finally compile these statements with ...
    • Scaling and Availability for Dynamic Content Web Sites 

      Amza, Cristiana; Cox, Alan; Zwaenepoel, Willy (2002-06-02)
      We investigate the techniques necessary for building highly-available, low-cost, scalable servers, suitable for supporting dynamic content web sites. We focus on replication techniques for scaling and availability of a dynamic content site using a cluster of commodity computers running Web servers and database engines. Our techniques allow scaling ...
    • Scaling e-Commerce Sites 

      Amza, Cristiana; Cox, Alan; Zwaenepoel, Willy (2002-02-19)
      We investigate how an e-commerce site can be scaled up from a single machine running a Web server and a database to a cluster of Web server machines and database engine machines. In order to reduce development, maintenance, and installation costs, we avoid modifications to both the Web server and the database engine, and we replicate the database on ...
    • Scheduling Algorithms Performance Evaluation in Grid Environments 

      Kennedy, Ken; Koelbel, Charles; Zhang, Yang (2006-04-18)
      Effective scheduling is critical for the performance of an application launched onto the Grid environment. Deriving efficient algorithms for this scheduling has always been a challenging research area. Many scheduling algorithms have been proposed, studied and compared but there are few studies comparing their performance in Grid environments. The ...
    • Scheduling Tasks to Maximize Usage of Aggregate Variables In Place 

      Budimlić, Zoran; Kennedy, Ken; Mahmeed, Samah; McCosh, Cheryl; Rogers , Steve (2006-08-21)
      We present an algorithm for greedy in-placeness that runs in O(TlogT + Ew V + V^2) time, where T is the number of in-placeness opportunities, Ew is the aggregate number of wire successors and v is the number of virtual instruments in a program graph.