Recursos de colección

DSpace at MIT (104.280 recursos)

This site is a university repository providing access to the publication output of the institution. Registered users can set up email alerts to notify them of newly added relevant content. A certain level of encryption and security is embedded in the site which may cause some users accessibility problems.

Computer Science (CS)

Mostrando recursos 1 - 20 de 107

  1. Provably Efficient Adaptive Scheduling for Parallel Jobs

    He, Yuxiong; Hsu, Wen Jing; Leiserson, Charles E.
    Scheduling competing jobs on multiprocessors has always been an important issue for parallel and distributed systems. The challenge is to ensure global, system-wide efficiency while offering a level of fairness to user jobs. Various degrees of successes have been achieved over the years. However, few existing schemes address both efficiency and fairness over a wide range of work loads. Moreover, in order to obtain analytical results, most of them require prior information about jobs, which may be difficult to obtain in real applications. This paper presents two novel adaptive scheduling algorithms -- GRAD for centralized scheduling, and WRAD for distributed scheduling....

  2. How to Do a Million Watchpoints: Efficient Debugging Using Dynamic Instrumentation

    Zhao, Qin; Amarasinghe, Saman P.; Rabbah, Rodric M.; Rudolph, Larry; Wong, Weng Fai
    Application debugging is a tedious but inevitable chore in any software development project. An effective debugger can make programmers more productive by allowing them to pause execution and inspect the state of the process, or monitor writes to memory to detect data corruption. The latter is a notoriously difficult category of bugs to diagnose and repair especially in pointer-heavy applications. The debugging challenges will increase with the arrival of multicore processors which require explicit parallelization of the user code to get any performance gains. Parallelization in turn can lead to more data debugging issues such as the detection of data...

  3. Finite Energy Survey Propagation for Constraint Satisfaction Problems

    Chieu, Hai Leong
    The Survey Propagation (SP) algorithm [1] has recently been shown to work well in the hard region for random K-SAT problems. SP has its origins in sophisticated arguments in statistical physics, and can be derived from an approach known as the cavity method, when applied at what is called the one-step replica symmetry breaking level. In its most general form, SP can be applied to general constraint satisfaction problems, and can also be used in the unsatisfiable region, where the aim is to minimize the number of violated constraints. In this paper, we formulate the SP-Y algorithm for general constraint...

  4. Collaborative Data Publishing and Searching System

    Ooi, Beng Chin; Yu, Bei; Li, Guoliang
    In this paper, we present a folksonomy-based collaborative data publishing and searching system. The system accepts data objects described with user-created metadata, called data units. The system supports flexible structure on the data units, and places no restrictions on the vocabulary used. We devise a generic table model for storing and representing the data units of various structures. We propose a framework for managing the data units and providing browsing, searching and querying services over them. We present our current approaches and discuss relevant research issues.

  5. Characterizing Protein Conformation Space

    Nigham, Anshul; Hsu, David; Latombe, Jean-Claude
    In this work, we propose a radical approach for exploring the space of all possible protein structures. We present techniques to explore the clash-free conformation space, which comprises all protein structures whose atoms are not in self-collision. Unlike energy based methods, this approach allows efficient exploration and remains general -- the benefits of characterization of the space apply to all proteins. We hypothesize that this conformation space branches into many small funnels as we sample compact conformations. We develop a compact representation the conformation space, and give experimental results that support our hypothesis. Potential applications of our method include protein...

  6. Automated Verification of Shape and Size

    Nguyen, Huu Hai; David, Cristina; Qin, Shengchao; Chin, Wei Ngan
    Despite their popularity and importance, pointer based programs remain a major challenge for program verification. In this paper, we propose an automated verification system that is concise, precise and expressive for ensuring the safety of pointer-based programs. Our approach uses user-definable shape predicates to allow programmers to describe a wide range of data structures with their associated size properties. To support automatic verification, we design a new entailment checking procedure that can handle well-founded inductive predicates using unfold/fold reasoning. We have proven the soundness and termination of our verification system, and have built a prototype system.

  7. Using Cyclic Memory Allocation to Eliminate Memory Leaks

    Nguyen, Huu Hai; Rinard, Martin C.
    We present and evaluate a new memory management technique for eliminating memory leaks in programs with dynamic memory allocation. This technique observes the execution of the program on a sequence of training inputs to find m-bounded allocation sites, which have the property that at any time during the execution of the program, the program only accesses the last m objects allocated at that site. The technique then transforms the program to use cyclic memory allocation at that site: it preallocates a buffer containing m objects of the type allocated at that site, with each allocation returning the next object in...

  8. Survival Techniques for Computer Programs

    Rinard, Martin C.
    Programs developed with standard techniques often fail when they encounter any of a variety of internal errors. We present a set of techniques that prevent programs from failing and instead enable them to continue to execute even after they encounter otherwise fatal internal errors. Our results indicate that even though the techniques may take the program outside of its anticipated execution envelope, the continued execution often enables the program to provide acceptable results to their users. These techniques may therefore play an important role in making software systems more resilient and reliable in the face or errors.

  9. Relaxing Routing Table to Alleviate Dynamism in P2P Systems

    Fang, Hui; Hsu, Wen Jing; Rudolph, Larry
    In dynamic P2P networks, nodes join and depart from the system frequently, which partially damages the predefined P2P structure, and impairs the system performance such as basic lookup functionality. Therefore stabilization process has to be done to restore the logical topology. This paper presents an approach to relax the requirement on routing tables to provide provably better stability than fixed structured P2P systems. We propose a relaxed Chord that keeps the O(logN) number of hops for greedy lookup, but it requires less stabilization overhead. It allows a tradeoff between lookup efficiency and structure flexibility without adding any overhead to the...

  10. Modeling Information Flow in Face-to-Face Meetings while Protecting Privacy

    Rudolph, Larry; Zhenghao, Chen
    Social networks have been used to understand how information flows through an organization as well as identifying individuals that appear to have control over this information flow. Such individuals are identified as being central nodes in a graph representation of the social network and have high "betweenness" values. Rather than looking at graphs derived from email, on-line forums, or telephone connections, we consider sequences of bipartite graphs that represent face-to-face meetings between individuals, and define a new metric to identify the information elite individuals. We show that, in our simulations, individuals that attend many meetings with many different people do...

  11. Programming with Exceptions in JCilk

    Danaher, John S.; Lee, I-Ting Angelina; Leiserson, Charles E.
    JCilk extends the Java language to provide call-return semantics for multithreading, much as Cilk does for C. Java's built-in thread model does not support the passing of exceptions or return values from one thread back to the "parent" thread that created it. JCilk imports Cilk's fork-join primitives spawn and sync into Java to provide procedure-call semantics for concurrent subcomputations. This paper shows how JCilk integrates exception handling with multithreading by defining semantics consistent with the existing semantics of Java's try and catch constructs, but which handle concurrency in spawned methods. JCilk's strategy of integrating multithreading with Java's exception semantics yields some...

  12. MPEG-2 in a Stream Programming Language

    Drake, Matthew; Hoffmann, Hank; Rabbah, Rodric; Amarasinghe, Saman P.
    Image and video codecs are prevalent in multimedia applications, ranging from embedded systems, to desktop computers, to high-end servers such as HDTV editing consoles. It is not uncommon however for developers create (from scratch) and customize their codec implementations for each of the architecture targets they intend their coders and decoders to run on. This practice is time consuming and error prone, leading to code that is not malleable or portable. In this paper we describe an implementation of the MPEG-2 codec using the StreamIt programming language. StreamIt is an architecture independent stream language that aims to improve programmer productivity,...

  13. Keyword Join: Realizing Keyword Search for Information Integration

    Yu, Bei; Liu, Ling; Ooi, Beng Chin; Tan, Kian Lee
    Information integration has been widely addressed over the last several decades. However, it is far from solved due to the complexity of resolving schema and data heterogeneities. In this paper, we propose out attempt to alleviate such difficulty by realizing keyword search functionality for integrating information from heterogeneous databases. Our solution does not require predefined global schema or any mappings between databases. Rather, it relies on an operator called keyword join to take a set of lists of partial answers from different data sources as input, and output a list of results that are joined by the tuples from input...

  14. Imitation Learning of Whole-Body Grasps

    Hsiao, Kaijen; Lozano-Pérez, Tomás
    Humans often learn to manipulate objects by observing other people. In much the same way, robots can use imitation learning to pick up useful skills. A system is detailed here for using imitation learning to teach a robot to grasp objects using both hand and whole-body grasps, which use the arms and torso as well as hands. Demonstration grasp trajectories are created by teleoperating a simulated robot to pick up simulated objects. When presented with a new object, the system compares it against the objects in a stored database to pick a demonstrated grasp used on a similar object. Both...

  15. Global Data Computation in a Dedicated Chordal Ring

    Wang, Xianbing; Teo, Yong Meng
    Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t

  16. Free Probability, Sample Covariance Matrices and Stochastic Eigen-Inference

    Edelman, Alan; Rao, N. Raj
    Random matrix theory is now a big subject with applications in many disciplines of science, engineering and finance. This talk is a survey specifically oriented towards the needs and interests of a computationally inclined audience. We include the important mathematics (free probability) that permit the characterization of a large class of random matrices. We discuss how computational software is transforming this theory into practice by highlighting its use in the context of a stochastic eigen-inference application.

  17. Dynamic Memory Optimization using Pool Allocation and Prefetching

    Zhao, Qin; Rabbah, Rodric; Wong, Weng Fai
    Heap memory allocation plays an important role in modern applications. Conventional heap allocators, however, generally ignore the underlying memory hierarchy of the system, favoring instead a low runtime overhead and fast response times. Unfortunately, with little concern for the memory hierarchy, the data layout may exhibit poor spatial locality, and degrade cache performance. In this paper, we describe a dynamic heap allocation scheme called pool allocation. The strategy aims to improve cache performance by inspecting memory allocation requests, and allocating memory from appropriate heap pools as dictated by the requesting context. The advantages are two fold. First, by pooling together...

  18. Design Issues in Internet 0 Federation

    Sollins, Karen R.; Li, Ji
    Internet 0 is proposed as a local area network that supports extremely small network devices with very little capacity for computation, storage, or communication. Internet 0 addresses the issue of connecting very small, inexpensive devices such as lightbulbs and heating vents with their controllers. To achieve this effectively, Internet 0 assumes both that operating between communicating end-nodes should not require third-party support, and that IP will be available all the way to those end-nodes. Several simplifying assumptions are made in Internet 0 to achieve this. The objective of this paper is to explore issues of design in a context where...

  19. De-Emphasis of Distracting Image Regions Using Texture Power Maps

    Su, Sara L.; Durand, Frédo; Agrawala, Maneesh
    We present a post-processing technique that selectively reduces the salience of distracting regions in an image. Computational models of attention predict that texture variation influences bottom-up attention mechanisms. Our method reduces the spatial variation of texture using power maps, high-order features describing local frequency content in an image. Modification of power maps results in effective regional de-emphasis. We validate our results quantitatively via a human subject search experiment and qualitatively with eye tracking data.

  20. BATON: A Balanced Tree Structure for Peer-to-Peer Networks

    Jagadish, H.V.; Ooi, Beng Chin; Rinard, Martin C.; Vu, Quang Hieu
    We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.