SIGDA E-News 1 August 2012, Vol. 42, No. 8

1 August 2012 :: ACM/SIGDA E-NEWSLETTER :: Vol. 42, No. 8
 Special Interest Group on Design Automation
1 August 2012, Vol. 42, No. 8
Online archive:
1. SIGDA News
    From: Lin Yuan <>
    From: Sudeep Pasricha <>

2. What is Robust Optimization?
    Contributing authors:
    Laleh Behjat <>, University of Calgary, Alberta
    Logan Rakai <>, University of Calgary, Alberta
    From: Srinivas Katkoori <>

3. Paper Submission Deadlines
    From: Debjit Sinha <>

4. Upcoming Conferences and Symposia
    From: Debjit Sinha <>

5. Upcoming Funding Opportunities
    From: Prabhat Mishra <>

6. Call for participation: ACM SIGDA CADathlon 2012
    From: Sudeep Pasricha <>

7. Call for participation: IEEE RTCSA 2012
    From: Sudeep Pasricha <>

8. 2012 CAV Award Announcement
    From: Matthew Guthaus <>

9. Call for participation: 2012 CAD Contest
    From: Zhuo Li <>

10. TAU 2012 Power Grid Simulation Contest results
    From: Zhuo Li <>
Comments from the Editors

Dear ACM/SIGDA members,

In this issue, we have a very interesting article on Robust Optimization.
If you are interested in contributing to this column in
the future, please contact Srinivas Katkoori <>.
An article only needs to be about 1 page long with several references.
All articles are included in the ACM digital library and there is no
restriction for the reproduction of the article for printed
publication later.

Sudeep Pasricha, E-Newsletter Editor;
Debjit Sinha, E-Newsletter Associate Editor;
Lin Yuan, E-Newsletter Associate Editor;
Srinivas Katkoori, E-Newsletter Associate Editor
Prabhat Mishra, E-Newsletter Associate Editor

Back to Contents

"Synopsys Acquires Ciranova"
Synopsys, Inc. (Nasdaq: SNPS), a world leader in software and IP used in
the design, verification and manufacture of electronic components and systems,
announced today that it has completed the acquisition of Ciranova, a privately held
electronic design automation (EDA) company focused on delivering productivity
improvements in custom IC design by reducing the time and effort needed
to develop transistor-level layout on advanced nodes.

"Cadence Acquires Sigrity, a Leader in High-Speed PCB and IC Packaging
Cadence Design Systems, Inc. (NASDAQ: CDNS), a leader in global electronic
design innovation, today announced it has acquired Sigrity, Inc., a leading
signal and power integrity technology provider. Sigrity provides a rich
set of gigabit signal and power network analysis technologies, including a
unique power-aware signal integrity analysis capability for system, printed
circuit board (PCB), and IC package designs.

"Analog sector to post modest sales growth, boost 300-mm production"
The worldwide analog semiconductor market is on track this year to grow 5.1
percent, increasing at a slower clip than the overall semiconductor industry,
according to a market report from Semico Research Corp. Revenue is expected to
reach $44.48 billion, compared with $42.34 billion in 2011. Semico, however,
forecasts stronger growth in 2013 with revenue exceeding $50 billion, putting
the growth rate in the double-digits at 12.6 percent. Analog revenue is
heavily weighted to communications products, but there are several market
growth drivers, including automotive, energy, mobility and medical/healthcare.

"Researchers claim smallest semiconductor laser"
Physicists at the University of Texas-Austin say they have developed the
world's smallest semiconductor laser in collaboration with colleagues in Taiwan
and China. The researchers say the development is a breakthrough for emerging
photonic technology with applications from computing to medicine. "We have
developed a nanolaser device that operates well below the 3-D diffraction
limit," said Chih-Kang "Ken" Shih, professor of physics at the University
of Texas, in a statement. "We believe our research could have a large impact
on nanoscale technologies."

"Samsung eating Apple's smartphone iLunch"
Samsung Electronics Co. Ltd. has regained the lead in the smartphone market
in 2Q12, six months after losing out to Apple, according to market research firm
IHS-iSuppli (El Segundo, Calif.).

"IEEE forecasts ten-fold data growth by 2015"
Data traffic is expected to grow ten-fold from 2010 to 2015 and up to 100-fold
by 2020, according to a new report from the IEEE's Ethernet standards
group. The assessment aimed to lay a foundation for future work on Ethernet
interfaces beyond today's 40 and 100 Gbit/second standards.

"Expert, lawmakers at odds over GPS security"
After testifying before Congress about security vulnerabilities in civil
GPS systems last week, Todd Humphreys is convinced the industry needs a new
approach to plugging holes in what he calls "the most popular unauthenticated
protocol in the world." "There’s a way to add backward-compatible
authentication like digital watermarks to GPS signals, and last week I had
my best shot at convincing lawmakers to fix the problem at the signal source,"
said Humphreys who directs the Radionavigation Laboratory at the University of
Texas at Austin.

"TSMC says single-customer fabs make sense"
The world's leading foundry chip maker Taiwan Semiconductor Manufacturing
Co. Ltd. is considering operating single-customer wafer fabs, according to
chairman and CEO Morris Chang. Chang, speaking to analysts on a conference call
to discuss the company's second quarter financial results, said that the market
is tending to produce fewer higher volume customers and some are so large they
need their own dedicated fabs. This is despite the fact that, as a foundry TSMC,
has risen on its ability to serve many customers from a single line.

"Power semi market worth $20B in 2012, says Yole"
The market for discrete semiconductors, module and ICs dedicated to the
power electronics industry will reach $20 billion in 2012, according to market
research firm Yole Developement (Lyon, France). The technology is addressing
applications from hybrid automobiles, through photovoltaic inverters to lighting,
heating and covers from single-digit voltages to thousands of volts. Yole
analysts reckon IGBTs account for $1.6 billion in the medium to high voltage
market. Superjunction MOSFETs present faster switching frequencies and the
market is set to be worth $567 million in 2012.

"Multi-screen wars: MediaTek/Mstar vs. Qualcomm, Marvell, Nvidia"
The larger significance of the merging of Taiwan’s "M Brothers" may have
escaped the notice of some western observers.

"DSP chip makes mobile sound louder"
An audio DSP chip from NXP Semiconductor NV (Eindhoven, The Netherlands)
is able to boost the output power of small speakers used in smartphones and
tablet computers by a factor of five while still preventing damage to the

"Updated: EDA firm gets funding after nine years"
Breker Verification Systems Inc. (Mountain View, Calif.), an EDA company
that provides verification software for system-chips, has announced it has
raised $5 million in Series A funding from Astor Capital Group.

"Hot Chips debuts new x86, Power, Sparc chips"
Engineers will get the first look inside new x86, Power and Sparc
microprocessors at the Hot Chips conference next month. The event will cast a
wide net that includes chips for cellular base stations and 3-D stacks.

"Micron claims first high-volume production of 45-nm PCM"
Claiming to offer the first phase change memory (PCM) in high-volume
production, U.S. memory chip vendor Micron Technology Inc. Tuesday (July 17)
announced the availability of a 45-nm multi-chip module for mobile devices
featuring PCM. Micron (Boise, Idaho) said its PCM solution for mobile devices
features 1-gigabit (Gb) PCM plus 512-megabit (Mb) LPDDR2 in a multi-chip package.

"Teardown: Inside Google's Nexus 7 tablet"
Amazon shook the consumer electronics market last year when it introduced
the first sub-$200 tablet, the Amazon Kindle Fire. Many were skeptical of the
online vendor’s foray into electronics, but some saw it as a stroke of genius.
By leveraging its vast library of online titles, Amazon set itself up to compete
on content with industry leader Apple.

"Search engine aims to quiz sensor networks"
A new type of search engine is being developed that can interrogate networks
of sensors to give real time answers to questions about the physical world. The
European-funded project, known as SMART, for 'Search engine for MultimediA
Environment geneRated content', aims to develop and implement an open source
system to allow internet users to search and analyse data from any network of

Back to Contents

What is Robust Optimization?

Laleh Behjat and Logan Rakai, University of Calgary, Alberta

In many stages of design automation, an optimization problem is solved, where
a certain objective such as area, power, wire length or skew is minimized.
The parameters and the variables of the optimization models are normally
considered to be deterministic. However, there can be inherent uncertainties
in the parameters or variables. For example, the length of a gate might be
nominally assigned 45 nm, but, during the fabrication, the actual length
can measure 20% lower or higher (between 36 to 54 nm). Major sources of
uncertainty include process variations, measurement errors, uncertainties
about future decisions, and partial access to information. Examples of
typical uncertainties in design automation are supply voltage variations,
manufacturing process variation and effects of thermal noise. In traditional
optimization techniques, these uncertainties are ignored and only nominal
solutions are obtained. These nominally optimal solutions can be very sensitive
to variation in parameters and can even cause infeasibility in practice [1].

Robust optimization techniques [1,2] try to obtain a balanced solution
considering all uncertainties. A robust solution is an optimized solution
when a set of uncertainties is considered. In the simplest form, a robust
solution can be thought of as resistant to uncertainties. Hence, a robust
solution can look inferior if directly compared to an individual nominally
optimal solution obtained under the assumption of perfect conditions. However,
when simulations that include uncertainty such as Monte Carlo simulations
or measurements of fabricated designs are performed, the robust solution
will show its superiority.

How to Solve a Problem Using Robust Optimization
The first step in producing a robust solution to a problem using robust
optimization is to identify and model the uncertainties in the system. The
source of uncertainty gives rise to different uncertainty sets. For example,
if the uncertainties are due to variations in the supply voltage, they may
be unknown but bounded. In other cases, such as uncertainty arising from
manufacturing defects, a distribution may be known.

The second step is to integrate uncertainties in the optimization problem. An
optimization problem that does not include uncertainty can be thought of as
finding an x that minimizes the objective f(x) subject to constraints g(x)
<= 0, where x represents the decision variables. A robust problem with
uncertainties in the constraints can be thought of as finding an x that
minimizes f(x) subject to g(x,u) <= 0, where u is allowed to vary over
all uncertainties in the uncertainty set. Because the constraints must be
satisfied for every u in the uncertainty set, the problem is optimized for
the worst case of uncertainties. If uncertainties are also in the objective
function, the worst-case robust optimization solution is the value of x that
minimizes the objective f(x,u) over all possible values of uncertainty u
subject to g(x,u) <= 0.

The final step in solving a robust optimization problem is finding a solution.
Although the uncertainty set being considered may produce a problem that is
not computationally tractable, there are many practical cases that produce
optimization problems that can be efficiently solved. In these tractable
cases, solvers implementing state-of-the-art algorithms are available to find
the robust solution to the given problem [3,4]. In some other cases where
the problem is not tractable, it may be possible to efficiently compute a
robust feasible, but not necessarily optimal solution [2].

Difference Between Stochastic and Robust Optimization
Stochastic optimization techniques have been used in applications where
uncertainty exists. However, a requirement to use stochastic optimization is
to confine the variations to a probabilistic model. In robust optimization,
the uncertainty model is a set, and the solution is optimal considering all
members of the set. Hence, robust optimization can be easier to solve and more
effective if a design must perform well under all realizations of uncertainty.
Robust optimization can also be used when the nature of uncertainty is not
probabilistic, or a distribution is not available, not accurately known,
or known but leading to intractable computational models.

Applications of Robust Optimization in Design Automation
A method using robust optimization to perform gate sizing over multiple corners
is presented in [5]. For this problem, the uncertainty is modeled by a set of
corners. Each corner assigns values to environmental parameters and process
parameters, such as temperature and threshold voltage, respectively. Equations
representing the delays of the circuit are derived for each corner. By
replicating the constraints for each corner in the optimization problem,
the uncertainty is accounted for. The resulting gate sizing solution is the
best that can be achieved for all corners.

Another gate sizing application of robust optimization is in [6]. In this work,
the uncertainty is in the size of gates after manufacturing. The uncertainty
is modeled using ellipsoidal uncertainty sets and can include intra-die
correlations in manufacturing defects, which affect the resulting gate sizes.

A technique for yield optimization under process variation is discussed
in [7]. In this work, a joint design-time and post-silicon minimization
on parametric yield loss using adjustable robust optimization is
discussed. Uncertainties in gate sizes and threshold voltages are dealt with
while minimizing leakage power.

[1] A. Ben-Tal and A. Nemirovski. Robust solutions of linear programming
problems contaminated with uncertain data. Math. Programming, 88:411–424,
[2] D. Bertsimas, D. Brown, and C. Caramanis. Theory and applications of
robust optimization. SIAM review, 53:464-501, 2011.
[3] MOSEK., accessed on July 23rd, 2012.
accessed on July 23rd, 2012.
[5] S. Boyd, S. Kim, D. Patil, and M. Horowitz. Digital circuit optimization
via geometric programming. Operations Research, 53:899–932, 2005.
[6] J. Singh, V. Nookala, Z. Luo, and S. Sapatnekar. Robust gate sizing by
geometric programming. In Proc. of DAC, pages 315–320, 2005.
[7] M. Mani, A. Singh, and M. Orshanksy. Joint design-time and post-silicon
minimization on parametric yield loss using adjustable robust optimization. In
Proc. ICCAD, 19-26, 2006.

Back to Contents

Paper Submission Deadlines

DATE'13 - Design Automation and Test in Europe
Grenoble, France
Deadline: Sep 9, 2012
Mar 18-22, 2013

ISSCC'13 - Int'l Solid-State Circuits Conference
San Francisco, CA
Deadline: Sep 10, 2012
Feb 17-21, 2012

ISQED'13 - Int'l Symposium on Quality Electronic Design
Santa Clara, CA
Deadline: Sep 12, 2012
Mar 11-13, 2013

ISCAS'13 - Int'l Symposium on Circuits and Systems
Beijing, China
Deadline: Sep 28, 2012
May 19-23, 2013

ASYNC'13 – Int’l Symposium on Asynchronous Circuits and Systems
Santa Monica, CA
Deadline: Dec 14, 2012 (Abstracts due: Dec 7, 2012)
May 19-22, 2013

MSE'13 - Microelectronics Systems Education
Austin, TX
Deadline: Jan 15, 2013
Jun 2-3, 2013

Back to Contents

Upcoming Conferences and Symposia

PACT'12 - Int'l Conference on Parallel Architectures and Compilation
Minneapolis, MN
Sep 21-25, 2012

BodyNets'12 – Int’l Conference on Body Area Networks
Oslo, Norway
Sep 24-26, 2012

VLSI-SoC’12 – Int’l Conference on Very Large Scale Integration and
System on Chip
Santa Cruz, CA
Oct 7-12, 2012

ESWEEK'12 - Embedded Systems Week (CASES, CODES+ISSS, and EMSOFT)
Tampere, Finland
Oct 7-12, 2012

Wireless Health’12
San Diego, CA
Oct 22-25, 2012

ICCAD’12 – Int’l Conference on Computer-Aided Design
San Jose, CA
Nov 5-8 2012

HLDVT’12 – Int’l High-Level Design, Validation and Test Workshop
Huntington Beach, CA
Nov 9-10, 2012

BIOCAS'12 - Biomedical Circuits and Systems Conference
Hsinchu, Taiwan
Nov 28-30, 2012

MICRO'12 - Int'l Symposium on Microarchitecture
Vancouver, Canada
Dec 1-5, 2012

ICFPT'12 - Int'l Conference on Field-Programmable Technology
Seoul, Korea
Dec 10-12, 2012

ICPADS'12 - Int'l Conference on Parallel and Distributed Systems
Singapore, Singapore
Dec 17-19, 2012

HiPC'12 - Int'l Conference on High Performance Computing
Pune, India
Dec 18-21, 2012

ISED’12 – Int’l Symposium on Electronic System Design
Kolkata, India
Dec 19-22, 2012

VLSI'13 - Int'l Conference on VLSI Design
Pune, India
Jan 5-10, 2013

HiPEAC'13: Int'l Conference on High Performance Embedded Architectures &
Berlin, Germany
Jan 21-23, 2013 hipeac2013

ASP-DAC'13 - Asia and South Pacific Design Automation Conference
Yokohama, Japan
Jan 22-25, 2013

Back to Contents

Upcoming Funding Opportunities


Office of Naval Research (ONR) Summer Faculty Research Program
Deadline: December 05, 2012

National Defense Science and Engineering Graduate (NDSEG) Fellowship Program
Deadline: December 16, 2012

Office of Naval Research (ONR) Sabbatical Leave Program
Deadline: Continuous

Naval Research Laboratory (NRL) Postdoctoral Fellowship Program
Deadline: Continuous


Microsystems Technology Office-Wide Broad Agency - DARPA-BAA-10-35
Deadline: September 1, 2012


Advanced Computing Initiative (ACI)
Deadline: September 12, 2012

Robust Computational Intelligence - AFOSR-BAA-2012-01
Deadline: Continuous

Systems and Software - AFOSR-BAA-2012-01
Deadline: Continuous

ERDC BAA - Computational Science and Engineering (ITL-1)
Deadline: Continuous

Advanced Distributed Sensor Technologies - BAA 57-09-06
Deadline: Continuous

Information Management and Decision Architectures (NRL-WIDE BAA-N00173-01)
Deadline: Continuous

High Performance Computing on Massively Parallel Architectures (BAA 64-09-01)
Deadline: Continuous

ASEE-NRL Postdoctoral Fellowship Program
Deadline: N/A

Multidisciplinary University Research Initiative (MURI)
Deadline: September 15, 2012


Resilient Extreme-Scale Solvers ("RX-Solvers")
Deadline: August 13, 2012

Early Career Research Program
Deadline: September 01, 2012

Director's Postdoctoral Fellows
Deadline: Continuous

Postdoctoral Appointments
Deadline: N/A

Sabbaticals and Faculty Appointments
Deadline: continuous

McDonnell Foundation

Studying Complex Systems - 21st Century Science Collaborative Activity Awards
Deadline: continuous

Alfred P. Sloan Foundation

Sloan Research Fellowships
Deadline: September 15, 2012


Research Experiences for Undergraduates (REU)
Deadline: September 15, 2012

National Robotics Initiative (NRI)
Deadline: October 01, 2012

Information and Intelligent Systems (IIS): Core Programs
Deadline: Oct 9 (medium) / Nov 30 (large) / Dec 17 (small), 2012

Computer and Network Systems (CNS): Core Programs
Deadline: Oct 9 (medium) / Nov 30 (large) / Dec 17 (small), 2012

Computing and Communication Foundations (CCF): Core Programs
Deadline: Oct 9 (medium) / Nov 30 (large) / Dec 17 (small), 2012

CISE Computing Research Infrastructure (CRI)
Deadline: October 23, 2012

Expeditions in Computing
Deadline: October 23, 2012

Energy, Power and Adaptive Systems (EPAS)
Deadline: November 1, 2012

Communications, Circuits, and Sensing-Systems (CCSS)
Deadline: November 1, 2012

Research and Evaluation on Education in Science and Engineering (REESE)
Deadline: Continuous

Back to Contents

Call for participation: ACM SIGDA CADathlon 2012

ACM SIGDA CADathlon 2012
Sunday, November 4

The CADathlon is a challenging, all-day, programming competition
focusing on practical problems at the forefront of Computer-Aided
Design, and Electronic Design Automation in particular. The contest
emphasizes the knowledge of algorithmic techniques for CAD
applications, problem-solving and programming skills, as well as

In its eleventh year as the "Olympic games of EDA," the contest brings
together the best and the brightest of the next generation of CAD
professionals. It gives academia and the industry a unique perspective
on challenging problems and rising stars, and it also helps attract
top graduate students to the EDA field.

The contest is open to two-person teams of graduate students
specializing in CAD and currently full-time enrolled in a
Ph.D. granting institution in any country. Students are selected
based on their academic backgrounds and their relevant EDA programming
experiences. Travel grant s are provided to qualifying students.The
CADathlon competition consists of six problems in the following areas:

(1) Circuit analysis
(2) Physical design
(3) Logic and behavioral synthesis
(4) System design and analysis
(5) Functional verification
(6) Bio-EDA

More specific information about the problems and relevant research
papers will be released on the Internet one week prior to the
competition. The writers and judges that construct and review the
problems are experts in EDA from both academia and industry. At the
contest, students will be given the problem statements and example
test data, but they will not have the judges' test data. Solutions
will be judged on correctness and efficiency. Where appropriate,
partial credit might be given. The team that earns the highest score
is declared the winner. In addition to handsome trophies, the first
place team's prize is a $2,000 cash award. The second place team's
prize is a $1,000 cash award.

Contest winners will be announced at the ICCAD Opening Session on
Monday morning and celebrated at the ACM/SIGDA Dinner and Member
Meeting on Monday evening.

The CADathlon competition is sponsored by ACM/SIGDA and several
Computer and EDA companies. For detailed contest information and
sample problems from last year's competition, please visit the ACM/
SIGDA website at


October 3 Participation request for submission due
October 8 Notification of acceptance


Chair, Jarrod Roy,
Vice Chair, Asst. Prof. Sudeep Pasricha,
Vice Chair, Assoc. Prof. Srinivas Katkoori,
Vice Chair, Sudarshan Banerjee,

Back to Contents

Call for participation: IEEE RTCSA 2012


RTCSA 2012
The 18th IEEE International Conference on Embedded and
Real-Time Computing Systems and Applications

August 19-22, 2012
Seoul National University
Seoul, Korea


The IEEE International Conference on Embedded and Real-Time Computing
Systems and Applications (RTCSA) provides a forum for sharing advanced
academic and industrial research work on embedded and real-time
systems, and ubiquitous computing applications. The conference has the
following goals: to investigate advances in embedded and real-time
systems and ubiquitous computing applications; to promote interaction
among the areas of embedded computing, real-time computing and
ubiquitous computing; and to evaluate the maturity and directions of
embedded and real-time system and ubiquitous computing technology.

This year the conference will be held in Seoul, Korea, on August 19-22,
at Seoul National University. Registration is open; for further
information please visit


* A strong technical program:

* Two affiliated workshops
- Cyber-Physical Systems, Networks, and Applications (CPSNA 2012)
- Power and Reliability in Multi-core Embedded Systems (PRIME 2012)

* Keynotes
- David (Kyungoh) Min, LG Electronics, Seoul, Korea
- Nikil Dutt, University of California, Irvine, United States

* Work-in-Progress session for new and creative approaches and ideas on
real-time systems and applications

Full details are on the conference Web site:


* Main Conference: Aug 20-22, 2012
* Workshops: CPSNA Aug 19, 2012
PRIME Aug 20, 2012
* Work-in-Progress Session: Aug 22, 2012
* Social Dinner: Aug 21, 2012


RTCSA 2011 recommends the SNU Hoam Faculty House (HFH), which is within
a short walking distance from the conference site. Hoam Faulty House

Seoul offers very good public transportation systems including bus and
subways. Any hotel nearby subways will be fine for commuting to the
conference site.

Steering Committee:
Tatsuo Nakajima, Waseda University, Japan (Chair)
Tei-Wei Kuo, National Taiwan University, Taiwan
Joseph K. Ng, Hong Kong Baptist University, China
Hide Tokuda, Keio University, Japan
Seongsoo Hong, Seoul National University, Korea
Sang H. Son, University of Virginia, USA

General Co-Chairs:
Yunheung Paek, Seoul National University, Korea
Jorgen Hansson, Chalmers University, Sweden

Program Co-Chairs:
Real-Time Systems: Steve Goddard, University of Nebraska-Lincoln, USA
Ubiquitous Comp/Cyber-Physical Systems: Chin-Fu Kuo, National University
of Kaohsiung, Taiwan
Embedded Systems: Jongeun Lee, UNIST, Korea

WIP Chair:
Chang-gun Lee, Seoul National University, Korea
Shinpei Kato, UC Santa Cruz, USA

Financial Chair:
Hyeonsang Eom, Seoul National University, Korea

Local Arrangement Chair:
Sung-Soo Lim, Kookmin University, Korea

Publication Chair:
Jangwoo Kim, Postech, Korea

Web Chair:
Neungsoo Park, Konkuk University, Korea

Publicity Co-Chairs:
Thomas Nolte, Malardalen University, Sweden (Europe)
Yoshinori Takeuchi, Osaka University, Japan (Asia)
Sudeep Pasricha, Colorado State University, USA (USA)

Back to Contents

2012 CAV Award Announcement

The 2012 CAV (Computer-Aided Verification) Award was presented on July 11,
2012, at the 24th annual CAV conference in Berkeley, California, to Sam
Owre, John Rushby, and Natarajan Shankar of SRI International. The annual
award, which recognizes a specific fundamental contribution or a series of
outstanding contributions to the CAV field includes a $10,000 award. The award
was presented with the citation: "for developing PVS (Prototype Verification
System) which, due to its early emphasis on integrated decision procedures
and user friendliness, significantly accelerated the application of proof
assistants to real-world verification problems."

The CAV conference is the premier international event for reporting research
on Computer-Aided Verification, a sub-discipline of Computer Science which is
concerned with ensuring that software and hardware systems operate correctly
and reliably. The CAV award was established in 2008 by the conference steering
committee and was given this year for the fifth time.

The Award-Winning Contribution

The design of automatic theorem provers has been one of the great challenges
in Computer Science since its beginnings, with the hope that computers -
by searching through infinite but well-defined spaces of formal proofs -
would be able to determine whether a mathematical hypothesis is a theorem
and, ultimately, discover interesting new mathematics. In parallel to the
difficult task of finding entire proofs automatically, much focus has been
on the more limited goal of building interactive proof assistants, which
are programs that support a user in constructing formal arguments and point
out gaps in the reasoning. Several such systems were already successful in
the early 1990s, when Sam Owre, John Rushby, and Natarajan Shankar of SRI
International built PVS (Prototype Verification System) - a proof assistant
that was specifically designed to be used in system verification.

In verification, proofs demonstrate the absence of errors in a software or
hardware system. Such proofs tend to overwhelm humans not by their mathematical
depth, but by the enormous number of steps, cases, side conditions, and the
like, which need to be considered. For a correctness proof to be completed
successfully, it is often more important for a computer to relieve the user
of simple steps and manage the overall progress of the argument, rather than
provide or check deep mathematical insights. At a time when much research
in computer-aided verification focused on semantic approaches such as model
checking, Owre, Rushby, and Shankar made proof assistants fashionable in
verification by building PVS around the following key elements:

1. An expressive, user-friendly, and well-documented system specification
2. Programmable tactics for automatically exploring promising proof directions
3. Decision procedures for common logical theories and their combination

Especially the third element - the pioneering conviction of the critical
importance of decision procedures, which automatically take care of many small,
but tedious steps in a proof - has proved prescient and led to an explosion
of research in decision procedures over past 20 years. Today, almost no
sizable verification project can succeed without decision procedures, and most
employ the help of proof management tools in one form or another. PVS paved
that way by orienting proof assistants toward greater speed and usability,
at a time when most others focused dogmatically on soundness.

PVS has found avid user communities especially in the verification of
safety-critical applications; real-time, distributed, and security protocols;
requirements engineering and software tools - all areas where both are
essential: (i) the ability, provided by expressive languages, to reason
about infinite-state systems and (ii) the automation provided by efficient,
integrated decision procedures. With this award, the CAV community recognizes
the historical importance of PVS and the associated paper "PVS: A Prototype
Verification System" by Sam Owre, John Rushby, and Natarajan Shankar, which
appeared at the Conference on Automated Deduction (CADE) in 1992.

CAV Conference
The CAV (Computer-Aided Verification) conference is an annual international
conference dedicated to the advancement of the theory and practice
of computer-aided formal analysis methods for hardware and software
systems. The conference covers the spectrum from theoretical results to
concrete applications, with an emphasis on practical verification tools and
the algorithms and techniques that are needed for their implementation. The
CAV conference was founded in 1989 by Edmund M. Clarke, Robert P. Kurshan,
Amir Pnueli, and Joseph Sifakis. The first CAV conference was hosted in 1989
in Grenoble, France, and since then it has been held in multiple sites in
North America, Europe, and the Middle East. This year's twenty-fourth CAV
conference was held in Berkeley, California, from July 7 to July 13, 2012.

Back to Contents

Call for participation: 2012 CAD Contest

Call for participation

The annual CAD Contest in Taiwan, sponsored by the Ministry of Education
(MOE), has been held for 12 consecutive years and has successfully boosted
the EDA research momentum in Taiwan. In 2012, we continue this great
tradition and internationalize it under the joint sponsorship of IEEE CEDA
and Taiwan MOE. The new contest, 2012 CAD Contest at ICCAD, is open
worldwide to have more significant contributions to our global EDA
community. You are invited to participate!


In the first year (2012), we design three contest problems covering three
distinct areas:

1. Finding the minimal logic difference for functional ECO contributed by
Taiwan Cadence Design Systems, Inc.
2. Design hierarchy aware routability-driven placement contributed by IBM
3. Fuzzy pattern matching for physical verification contributed by Mentor
Graphics Corp.


1. The contestants should be university students.
2. Contestants must register by August 16, 2012.
3. Changes of team members, advisors or topics should be made by the
deadline of registration.

Evaluation and ranking

1. Each topic is ranked separately.
2. The quality metrics are determined by the problem specifications,
including correctness, runtime and memory usage.
3. Each submitted program will be evaluated by the announced benchmarks and
hidden benchmarks.
4. The officially supported programming language will be C/C++. For other
languages, please check with the contest organizers first. MATLAB is
prohibited for use in the contest.
5. The library that can be used in the contest is the standard C/C++

6. System specification:

Linux version: TBD
Gcc version: TBD
GNU libc version: TBD


1. 1st Place
One team for each topic
- Certificate of 1st Place presented by ICCAD
- NTD50,000/team (approx. US$1650)
2. 2nd Place / 3rd Place
Two teams for each topic
- Certificate of 2nd Place presented by ICCAD
- NTD30,000/team (approx. US$1000)

(a) The reward amount in US dollars fluctuates slightly according to currency
(b)According to the tax law in Taiwan, 10% reward will be charged by tax
for the Taiwanese
taxpayers, while 20% will be charged by tax for foreign taxpayers.
(c)We reserve the right to change the number of prize winners.

Tentative Contest Schedule

1. Registration deadline August 16, 2012
2. Alpha submission 5pm CST (UTC+8), August 23, 2012
3. Submission deadline 5pm CST (UTC+8), September 24, 2012
4. Final announcement November 2012 (at ICCAD)

Other Information

1. For any other inquiries, please send emails to:
2. Please add "ICCAD2012_Contest" to the subject line for any emails regarding
the contest.
3. Any update will be announced on contest website:
4. There may be a special session organized for the contest at ICCAD 2012
(we will be notified by the end of May). This session includes three
presentations from the contest organizers for the three contest problems and
the award ceremony.


1. Contest chair:
Yih-Lang Li (National Chiao Tung University, Taiwan)

2. Co-chairs:
Iris Hui-Ru Jiang (National Chiao Tung University, Taiwan)
Zhuo Li (IBM, Corp.)

3. Topic chairs:
Jane Wang (Taiwan Cadence Design Systems, Inc.)
Natarajan Viswanathan (IBM Corp.)
Andres Torres (Mentor Graphics Corp.)


1. IEEE CEDA (Technical sponsorship)
2. Taiwan Ministry of Education (Financial sponsorship)

Back to Contents

TAU 2012 Power Grid Simulation Contest results

TAU 2012 Power Grid Simulation Contest has been successfully held from August
2011 to Jan 2012. This is the 2nd year of TAU Power Grid Simulation Contest,
which is organized by IBM Corp (Raju Balasubramanian, Zhuo Li and Frank
Liu), with the support from ACM TAU Workshop. The purpose of the contest
is to provide a unified venue to compare power grid simulators from each
participating team in terms of accuracy, runtime as well as memory usage. To
support the contest a number of real life industrial benchmarks extracted
from IBM internal integrated circuits were made public. For 2012, the contest
focused on transient analysis and parallel implementation. The details of
the contests can be found at,
and the final presentation presented at TAU 2012 workshop (Jan 18 to 20,
Taiwan) is at We congratulate the
winning teams for the TAU 2012 Power Grid Simulation Contest.

First place award: pgt_solver, University of Illinois at Urban-Champaign,
T. Yu, Martin D. F. Wong
Second place award: PowerRush, Tsinghua University, J. Yang, Z. Li, Y. Cai,
Q. Zhou
Third place award: IITPGS, Illinois Institute of Technology, X. Xiong, J. Wang.

Back to Contents

Notice to Authors

Notice to Authors By submitting your article for distribution in this Special Interest Group publication, you hereby grant to ACM the following non-exclusive, perpetual, worldwide rights: to publish in print on condition of acceptance by the editor; to digitize and post your article in the electronic version of this publication; to include the article in the ACM Digital Library and in any Digital Library related services; and to allow users to make a personal copy of the article for noncommercial, educational or research purposes. However, as a contributing author, you retain copyright to your article and ACM will refer requests for republication directly to you.

This newsletter is a free service for current SIGDA members and is added automatically with a new SIGDA membership.
Circulation: 2,700
This ACM/SIGDA E-NEWSLETTER is being sent to all persons on the ACM/SIGDA mailing list. To unsubscribe, send an email to with "signoff sigda-announce" (no quotes) in the body of the message. Please make sure to send your request from the same email as the one by which you are subscribed to the list.

To unsubscribe from the SIGDA-announce list, click the following link: