Now showing items 182-201 of 245

    • 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.
    • Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking 

      Druschel, Peter; Du, Shu; Johnson, David B.; Khan, Muhammed; PalChaudhuri, Santashil; (2005-02-08)
      As wireless devices become more pervasive, mobile ad hoc networks are becoming increasingly important, motivating the development of highly scalable ad hoc networking techniques. In this paper, we present the design and evaluation of a novel protocol for scalable routing in ad hoc networks, as part of the Safari project. Safari leverages and integrates ...
    • Separators in Graphs with Negative and Multiple Vertex Weights 

      Djidjev, Hristo N.; Gilbert, John (1994-04)
      A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems hold for several classes of graphs, including graphs of bounded genus and chordal graphs. We show that any separator theorem implies various weighted separator ...
    • Set-Based Analysis for Full Scheme and Its Use in Soft-Typing 

      Felleisen, Matthias; Flanagan, Cormac (1995-10)
      Set-Based Analysis is an efficient and accurate program analysis for higher-order languages. It exploits an intuitive notion of approximation that treats program variables as sets of values. We present a new derivation of set-based analysis, based on a reduction semantics, that substantially simplifies previous formulations. Most importantly, the ...
    • Shared Memory Computing on Networks of SMPS 

      Li, Zhenghua (1997-09-09)
      Parallel systems supporting a shared memory programming interface have been implemented both in software and hardware. Hardware shared memory systems are fast, but generally expensive. Software shared memory systems are cheaper but slower. A clustered software shared memory system on a network of symmetric multiprocessors (SMP) is a hybrid solution ...
    • Soft Typing: An Approach to Type Checking for Dynamically Typed Languages 

      Fagan, Mike (1992-08)
      In an effort to avoid improper use of program functions, modern programming languages employ some kind of preventative type system. These type systems can be classified as either static or dynamic. Static type systems detect "ill-typed" program phrases at compile-time, whereas dynamic type systems detect "ill-typed" phrases at run-time. Static typing ...
    • Static Type Inference for Specialization in a Telescoping Compiler 

      Allen, Eric; Kennedy, Ken; McCosh, Cheryl; Taha, Walid (2004-09-01)
      The telescoping languages approach achieves high performance from applications encoded as high-level scripts. The core idea is to pre-compile underlying libraries to generate multiple variants optimized for use indifferent possible contexts including different argument types. This paper proposes a type inference algorithm that enables this kind of ...
    • Stochastic Instruction Scheduling 

      Schielke, Philip (2000-11-13)
      Instruction scheduling is a code reordering transformation used to hide latencies present in modern day microprocessors. Scheduling is often critical in achieving peak performance from these processors. The designer of a compiler's instruction scheduler has many choices to make, including the scope of scheduling, the underlying scheduling algorithm, ...
    • Stones Unturned: Gaps in the Investigation of Sarasota's Disputed Congressional Election 

      Dill, David L.; Wallach, Dan S. (2007-04-13)
      The November 2006 race for Florida’s 13th Congressional District resulted in a 369 vote margin of victory for the winning candidate with more than 18,000 undervotes recorded on the ES&S iVotronic touch-screen voting machines used in Sarasota County. Since then, the losing candidate and a coalition of local voters have filed suit against the state and ...
    • Strategy for Compiling Parallel Matlab for General Distributions 

      Fletcher, Mary; Jin, Guohua; Kennedy, Ken; McCosh, Cheryl (2006-06-16)
      Executing applications in parallel can produce significant performance gains, yet the time and expertise needed for the low-level details of parallelism is often prohibitive. Additionally, many applications rely heavily on domain-specific libraries, while it is not practical to write an optimizing compiler each time a domain-specific library is ...
    • Subdivision Schemes for Variational Splines 

      Warren, Joe; Weimer, Henrik (2000-02-14)
      The original theory of splines grew out of the study of simple variational problems. A spline was a function that minimized some notion of energy subject to a set of interpolation constraints. A more recent method for creating splines is subdivision. In this framework, a spline is the limit of a sequence of functions, each related by some simple ...
    • Supplemental Note on Count-to-Infinity Induced Forwarding Loops in Ethernet Networks 

      Cox, Alan L.; Elmeleegy, Khaled; Ng, T. S. Eugene (2006)
      In this document, we show that the count to infinity behavior in the RSTP protocol can lead to a temporary forwarding loop in an Ethernet network.