Candidate 5:
Speaker:
Dr. Sri. Parthasarathy, University of Maryland
Title:
Unified algorithms for combinatorial optimization in large-scale distributed systems
Date and Time: May 8, 2006, 3:00 pm
Place: 164 Coates
Abstract: A central question in large-scale distributed systems is as follows: how
can we partition scarce resources in the sytem across competing users, so
that individual users are satisfied and certain system-wide metrics of
interest are optimized? Such combinatorial optimization problems arise in
a variety of settings such as large-scale
storage systems, health care systems, ad hoc / peer-to-peer networks, and high-performance
simulations of physical, biological, and epidemiological phenomena. In this talk, I will
describe the use of two sophisticated algorithm design paradigms, namely,
Linear Programming (LP) based optimization, and randomization, for
addressing such large-scale system design challenges.
In the first part of my talk, I will consider throughput optimization in
wireless networks; I will present provably-good algorithms for estimating
the throughput capacity of wireless networks, and routing and scheduling
algorithms which are guaranteed to operate the network close to its
capacity. In the second part of my talk, I will describe my work on
assignment algorithms. I will present a single unified assignment
algorithm for handling a broad variety of assignment problems; this
algorithm is derived through a fusion of linear algebra and randomization,
and generalizes many seminal and classical approaches for assignment known
in the literature.
Biodata: Sri is receiving Ph.D. in the Department of
Computer Science at University of Maryland (UMD), College Park. His
research broadly focuses on algorithm design and optimization, and their
applications to large-scale systems. His interests include combinatorial
optimization, randomized / approximation algorithms, networking, modeling
and analysis of physical and biological processes, and information
retrieval. His research highlights include receiving the University of
Maryland -- Dean's fellowship award for excellence in research, travel
awards from the ACM and IEEE professional societies, and peer-reviewed
publications in several top journals and conferences including the Journal
of the ACM, FOCS '05, FOCS '02, SIGMETRICS '05, ICDCS '05, IPDPS '05, and
SODA '04. He holds an M.S. in computer science from University of
Maryland(2003), and B. Tech in Computer Science and Engineering from the
Indian Institute of Technology, Madras, India (2000).
Candidate 4:
Speaker:
Mr. David P. Bunde, University of Illinois at Urbana-Champaign
Title:
Power-aware scheduling
Date and Time: April 5, 2006, 1:15 pm
Place: 164 Coates
Abstract: Power consumption has always been a major issue for users of laptops
and other mobile devices, but its importance has increased over time
because processor power consumption has grown faster than battery
capacity. To cope with this problem, processors for some mobile
devices now incorporate speed scaling. Speed scaling allows the
processor to lower its clock speed, which extends battery life but
lowers system performance. An important question is how to make this
tradeoff to achieve the best possible performance given a battery's
limited power supply.
In this talk, I discuss algorithms to schedule jobs and assign
processor speeds under two measures of schedule quality.
Specifically, I consider makespan, the completion time of the last
job, and total flow, the sum of times between job arrival and
completion. My main results are a linear-time algorithm to minimize
makespan on a single processor and an extension of that algorithm to
multiprocessors for equal-work jobs. The same techniques also give an
arbitrarily-good approximation for minimizing the total flow of
equal-work jobs on a multiprocessor. Finally, I show that exactly
minimizing total flow is impossible even for uniprocessor instances
with equal-work jobs in a model of computation allowing exact real
arithmetic.
Biodata: David P. Bunde is a graduate student in the CS Department at the University of Illinois at Urbana-Champaign (UIUC). He is part of the
theory group and his advisor is Jeff Erickson. His main research interest is scheduling, but he has also published in
processor allocation, admission control, and algorithmic graph theory. For more details please visit
http://compgeom.cs.uiuc.edu/~bunde/ .
Candidate 3:
Speaker: Xiaotong Zhuang , Georgia Institute of Technology
Title: Compiler Optimizations for Network Processors
Date and Time: March 27, 2006, 3:00 pm
Place: 164 Coates
Abstract:
In this presentation, I will mainly talk about my research on code
optimizations for network processors. The dramatic growth of Internet applications has prompted
the need for a new category of processors called Network
Processors (NPs). NPs are multi-threaded processors
with fast processing speed and specialized hardware support for network applications.
Due to very high clocking speeds, the memory gap on this
network processor is huge, making registers extremely precious.
Moreover, the register file is split into two banks, and for
any ALU instruction, the two source operands must come from
different banks. We introduce the notion of a register conflict graph (RCG),
which captures the dual-bank constraint. Generally, the problem
is to break odd cycles on the RCG with minimal performance
loss. We also present and compare three different approaches
to do register allocation and bank assignment. This work was built as a post-pass optimizer for Intel's
IXP 1200 series and subsequently implemented by Intel in their research compiler.
Next, I will briefly present my research on secure processors. Secure processors have recently been
introduced as a mechanism to provide copy and tamper resistant execution. We found that
the original secure processor model is severely crippled if
the address bus is not properly protected and proposed two solutions to solve the problem.
Biodata:
Xiaotong Zhuang is a doctoral student in the Computer Science department of
Georgia Institute of Technology. Xiaotong also holds a BE degree in EE from
Shanghai Jiaotong Univervisty, and two MS degrees in CS from Shanghai
Jiaotong Univervisty and Georgia Institute of Technology respectively. His
main research focus is on compilers. He is also interested in parallel and
distributed computing, computer security. During his PhD study, he has conducted
research in many emerging areas such as network processors, secure architecture,
power-aware computing. As a result of this endeavor, he has published over 25
papers in conferences and journals.
Candidate 2:
Speaker:
Dr. D. Wang, University of Texas at Dallas, Research
staff at Green Hills Software Inc., Santa Barbara, CA
Title:
Automated System Design for Ultra-High Dependability Assurance Based on Independently
Developable End-User Assessable Logical (IDEAL) Aspects
Date and Time: March 24, 2006, 3:00 pm
Place: 164 Coates
Abstract: Software system is becoming more and more complicated and safety-critical, which makes it
necessary to be able not only to achieve high system reliability but also to rigorously demonstrate that
high system reliability has in fact been achieved. Considering this requirement, my research proposes a
novel model, namely, Relational Program Architecture, which aims at achieving ultra-high system reliability
and dependability assurance. In the relational program architecture, a system is composed from several
aspects, each of which can be not only independently developable, but is also amenable to end-user
assessment, i.e., the end-user can certify each aspect by directly observing and comparing its behavior
with the expected behavior even though it might be a part of a very large system. We refer to these aspects as
Independently Developable End-User Assessable Logical (IDEAL) aspects. The overall system properties, such
as system safety, stability, and reliability, can be directly inferred from the properties of the individual
IDEAL aspects so that the integration testing and verification of the entire system is not needed. Since
each IDEAL aspect can be solved and validated in its restricted "view" of the system, it is easier to
implement and verify each individual IDEAL aspect compared with the entire system. Based on the relational
program architecture, I have developed a new design method. This design method is automated, i.e.,
the IDEAL aspects of a system can be automatically synthesized through the specification of the system.
Also, this design method is aspect-oriented, meaning that it designs a system based on aspects instead of
other popular concepts, such as objects, procedures, agents, etc.
Biodata:
Dongfeng Wang is currently a member of research staff at Green Hills Software Inc. In August 2005, he
received his Ph.D. degree in Computer Science from the University of Texas at Dallas. His main research
focuses on Software Engineering. He is also interested in System Reliability, Fault-Tolerant System,
and Trust Computing.
Candidate 1:
Speaker:
Mr. Jinlin Yang , University of Virginia
Title:
Perracotta: Automatic Inference and Effective Application of Temporal Specifications
Date and Time: March 9, 2006, 3:00 pm
Place: 164 Coates
Abstract:
Program verification techniques have shown great effectiveness for finding
generic program defects such as illegal pointer usages and been adopted by
many industrial software companies. Such techniques, however, have only
achieved little success for detecting application-specific defects due to the
unavailability of the rule specifications. This limitation not only prevents
the wide adoption of program verification tools, but also lets many
bugs escape into production code. One important class of rules is temporal
specifications that constrain the order of occurrence of events. Satisfying
them is essential for a program's correctness. I developed a dynamic analysis
technique to automatically infer simple temporal rules of a program.
I generate execution traces of the program by running a set of test cases
and then analyze the properties satisfied by traces using inference techniques
and a set of predefined patterns. Focusing on enabling effective dynamic
inference on large programs under realistic conditions,
my approach made three contributions over previous work. First, my inference
algorithm scales well to large execution traces. Second, my statistical
inference algorithm can successfully deal with imperfect traces caused by buggy
programs or inadequate profiling environment. Third, I developed a set of
heuristics for effectively winnowing the large number of properties inferred
to a manageable set of interesting properties. I have implemented our dynamic
analysis technique in a prototype tool called Perracotta. To evaluate the
usefulness of dynamically inferred temporal properties, I applied them to aid
program understanding, verification, and evolution. For program understanding, I
used Perracotta on the JBoss transaction manager module to infer a 24-state
finite state machine that is consistent with the J2EE specification.
For program verification, I inferred interesting API rules for the Windows kernel
and discovered many previously unknown bugs in Windows by checking the inferred
properties with the ESP verifier. For program evolution, I used the inferred
properties to show important behavioral differences among six versions of OpenSSL.
Biodata:
Jinlin Yang is a PhD candidate in the Department of Computer Science at the
University of Virginia. His research interests are in software engineering,
programming languages, and security with a focus on program analysis,
verification, and testing. He was an intern at the Center for Software
Excellence at the Microsoft Corporation in summer 2005. He received a
Master’s degree in Computer Science from the University of Virginia in
2004 and a Bachelor’s degree in Computer Science and Technology from the
Tsinghua University in Beijing, China in 2001.please visit
http://www.cs.virginia.edu/~jy6q/ for more details.
