Select a calendar:
Filter May Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for May 06, 2013
-
PhD Defense - Manaschai Kunaseth
Mon, May 06, 2013 @ 10:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
University Calendar
PhD Candidate: Manaschai Kunaseth
Time: 10:00am-12:00pm, Monday, May 6, 2013
Location: SSL 104
Committee:
Robert F. Lucas
Aiichiro Nakano (Chair)
Katherine Shing
Title:
Metascalable Hybrid Message-Passing and Multithreading Algorithms for n-Tuple Computation
Abstract:
The emergence of the multicore era has granted unprecedented computing capabilities. Extensively available multicore clusters have influenced hybrid message-passing and multithreading parallel algorithms to become a standard parallelization for modern clusters. However, hybrid parallel applications of portable scalability on emerging high-end multicore clusters consisting of multimillion cores are yet to be accomplished. Achieving scalability on emerging multicore platforms is an enormous challenge, since we do not even know the architecture of future platforms, with new hardware features such as hardware transactional memory (HTM) constantly being deployed. Scalable implementation of molecular dynamics (MD) simulations on massively parallel computers has been one of the major driving forces of supercomputing technologies. Especially, recent advancements in reactive MD simulations based on many-body interatomic potentials have necessitated efficient dynamic n-tuple computation. Hence, it is of great significance now to develop scalable hybrid n-tuple computation algorithms to provide a viable foundation for high-performance parallel-computing software on forthcoming architectures.
This dissertation research develops a scalable hybrid message-passing and multithreading algorithm for n-tuple MD simulation, which will continue to scale on future architectures (i.e. achieving metascalability). The two major contributions of this dissertation research are: (1) design a scalable hybrid message-passing and multithreading parallel algorithmic framework on multicore architectures and evaluate it on most advanced parallel architectures; and (2) develop a computation-pattern algebraic framework to design scalable algorithms for general n-tuple computation and prove its optimality in a systematic and mathematically rigorous manner. We expect that the proposed hybrid algorithms and mathematical approaches will provide a generic framework to a broad range of applications on future extreme-scale computing platforms.
Location: Seaver Science Library (SSL) - 104
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
-
PhD Defense - Dirk Hovy
Mon, May 06, 2013 @ 01:30 PM - 03:30 PM
Thomas Lord Department of Computer Science
University Calendar
Learning Semantic Types and Relations from Text
Committee: Jerry Hobbs (chair), Elsi Kaiser (external), Dennis McLeod, Kevin Knight, David Chiang
NLP applications such as Question Answering (QA), Information Extraction (IE), or Machine Translation (MT) are incorporating increasing amounts of semantic information. A fundamental building block of semantic information is the relation between a predicate and its arguments, e.g. eat(John,burger). In order to reason at higher levels of abstraction, it is useful to group relation instances according to the types of their predicates and the types of their arguments. For example, while eat(Mary,burger) and devour(John,tofu) are two distinct relation instances, they share the underlying predicate and argument types INGEST(PERSON,FOOD).
A central question is: where do the types and relations come from?
The subfield of NLP concerned with this is relation extraction, which comprises two main tasks:
1. identifying and extracting relation instances from text
2. determining the types of their predicates and arguments
The first task is difficult for several reasons. Relations can express their predicate explicitly or implicitly. Furthermore, their elements can be far part, with unrelated words intervening. In this thesis, we restrict ourselves to relations that are explicitly expressed between syntactically related words. We harvest the relation instances from dependency parses.
The second task is the central focus of this thesis. Specifically, we will address these three problems: 1) determining argument types 2) determining predicate types 3) determining argument and predicate types. For each task, we model predicate and argument types as latent variables in a hidden Markov models. Depending on the type system available for each of these tasks, our approaches range from unsupervised to semi-supervised to fully supervised training methods.
The central contributions of this thesis are as follows:
1. Learning argument types (unsupervised): We present a novel approach that learns the type system along with the relation candidates when neither is given. In contrast to previous work on unsupervised relation extraction, it produces human-interpretable types rather than clusters. We also investigate its applicability to downstream tasks such as knowledge base population and construction of ontological structures. An auxiliary contribution, born from the necessity to evaluate the quality of human subjects, is MACE (Multi-Annotator Competence Estimation), a tool that helps estimate both annotator competence and the most likely answer.
2. Learning predicate types (unsupervised and supervised): Relations are ubiquitous in language, and many problems can be modeled as relation problems. We demonstrate this on a common NLP task, word sense disambiguation (WSD) for prepositions (PSD). We use selectional constraints between the preposition and its argument in order to determine the sense of the preposition. In contrast, previous approaches to PSD used n-gram context windows that do not capture the relation structure. We improve supervised state-of-the-art for two type systems.
3. Argument types and predicates types (semi-supervised): Previously, there was no work in jointly learning argument and predicate types because (as with many joint learning tasks) there is no jointly annotated data available. Instead, we have two partially annotated data sets, using two disjoint type systems: one with type annotations for the predicates, and one with type annotations for the arguments. We present a semisupervised approach to jointly learn argument types and predicate types, and demonstrate it for jointly solving PSD and supersense-tagging of their arguments. To the best of our knowledge, we are the first to address this joint learning task.
Our work opens up interesting avenues for both the typing of existing large collections of triple stores, using all available information, and for WSD of various word classes.
Location: Hedco Neurosciences Building (HNB) - 100
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
-
Mor Harchol-Balter: Dynamic Power Management in Data Centers: Theory & Practice
Mon, May 06, 2013 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Mor Harchol-Balter, Carnegie Mellon University
Talk Title: Dynamic Power Management in Data Centers: Theory & Practice
Series: CS Colloquium
Abstract: Energy costs for data centers continue to rise, already exceeding ten billion dollars yearly. Sadly much of this power is wasted. Server are only busy 10-30% of the time, but they are often left on, while idle, utilizing 60% of more of peak power while in the idle state. The obvious solution is dynamic power management: turning servers off, or re-purposing them, when idle. The drawback is a prohibitive "setup cost" to get servers back "on." The purpose of this talk is to understand the effect of the "setup cost" and whether dynamic power management makes sense.
We first turn to theory and study the effect of setup cost in an M/M/k queue. We present the first analysis of the M/M/k/setup queueing system. We do this by introducing a new technique for analyzing infinite, repeating, continuous-time Markov chains, which we call Recursive Renewal Reward (RRR).
We then turn to implementation, where we implement and evaluate
dynamic power management in a multi-tier data center with key-value store workload, reminiscent of Facebook or Amazon. We propose a new dynamic algorithm, AutoScale, which is ideally suited to the case of unpredictable, time-varying load, and we show that AutoScale dramatically reduces power in data centers.
Joint work with: Anshul Gandhi, Alan Scheller-Wolf, and Mike Kozuch.
Biography: Mor Harchol-Balter is an Associate Professor in Computer Science at Carnegie Mellon University. From 2008-2011, she served as the
Associate Department Head for Computer Science. She received her
doctorate in Computer Science at U.C. Berkeley under the direction of Manuel Blum. She is a recipient of the McCandless Chair, the NSF CAREER award, the NSF Postdoctoral Fellowship in the Mathematical Sciences, multiple best paper awards, and several teaching awards, including the Herbert A. Simon Award for Teaching Excellence. She is heavily involved in the ACM SIGMETRICS performance research community, where she served as Technical Program Chair for Sigmetrics 2007 and is General Chair for Sigmetrics 2013.
Host: Leana Golubchik
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Assistant to CS chair
