A-Z Index | Phone Book | Careers

InTheLoop | 02.19.2013

The Weekly Newsletter of Berkeley Lab Computing Sciences

February 19, 2013

ESnet Contributes Ideas for Energy-Efficient Networking at International Roundtable

Since he joined ESnet in 2009, Inder Monga has been advocating approaches to assess and improve the energy efficiency of the national network. So when 27 of the world’s leading thinkers in energy-efficient networking gathered February 7–8 in Santa Barbara, it wasn’t surprising that ESnet’s Chief Technologist Monga was among those invited to share their ideas.

The day-and-a-half discussion on “ICT core networks: Towards a scalable, energy-efficient future” was an invitation-only meeting, convened by UC Santa Barbara’s Institute for Energy Efficiency. Attendees included representatives from network operators, equipment vendors, academia, research labs and government networks. ESnet was also one of the sponsors supporting the workshop. Read more.

NERSC Announces Winners of Inaugural HPC Achievement Awards

NERSC announced the winners of their inaugural High Performance Computing (HPC) Achievement Awards last Wednesday at the annual NERSC User Group meeting at Berkeley Lab. The awardees are all NERSC users who have either demonstrated an innovative use of HPC resources to solve a scientific problem, or whose work has had an exceptional impact on scientific understanding or society. In an effort to encourage young scientists who are using HPC in their research, NERSC also presented two early career awards. Read more.

Evaluation Framework Assesses Accuracy of Genome and Metagenome Assemblies

Researchers need general purpose methods for objectively evaluating the accuracy of single and metagenome assemblies and for automatically detecting any errors they may contain. Current methods do not fully meet this need because they require a reference, only consider one of the many aspects of assembly quality, or lack statistical justification, and none are designed to evaluate metagenome assemblies.

But now, researchers from Cornell University, the DOE Joint Genome Institute, and Berkeley Lab have developed an Assembly Likelihood Evaluation (ALE) framework that overcomes these limitations, systematically evaluating the accuracy of an assembly in a reference-independent manner using rigorous statistical methods. The research was performed using startup and production allocations at NERSC. The journal Bioinformatics published the article online on January 9, 2013. Scott Clark, the lead author at Cornell, was supported by a DOE SC Computational Science Graduate Fellowship.

Proton Delivery and Removal Can Speed Up or Slow Down a Common Catalyst

Proton delivery and removal determines if a well-studied catalyst takes its highly productive form or twists into a less useful structure, according to scientists at Pacific Northwest National Laboratory (PNNL). The nickel-based catalyst can take two protons and form molecular hydrogen, or it can split the hydrogen — important reactions for fuel cells and biofuel production.

Experiments using nuclear magnetic resonance spectroscopy and simulations performed at NERSC and two other DOE computing centers showed that the most productive isomer has the key nitrogen-hydrogen bonds pushed close to the nickel center. In this form, the reaction occurs in a fraction of a second. If the catalyst is stuck in another form, the reaction takes days to complete.

“When we started on the research, there was the belief that breaking or forming hydrogen was the crucial step,” says Simone Raugei, a PNNL theoretician. “It isn’t. It is putting protons in the right spot on the catalyst. Once you have them in the right spot, everything goes very quickly.” Read more.

Yelick to Deliver Keynote, Other Staff Contribute to Parallel Programming Symposium

Kathy Yelick, the Associate Laboratory Director for Computing Sciences, has been invited to give the keynote address at PPoPP’13, the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Yelick with discuss “Antisocial Parallelism: Avoiding, Hiding and Managing Communication” on Tuesday, Feb. 26. Sponsored by the ACM’s Special Interest Group on Programming Languages, PPoPP is a forum for leading work on all aspects of parallel programming, including foundational and theoretical aspects, techniques, tools, and practical experiences. PPoPP’13 will be held February 23–27 in Shenzhen, China.

According to Yelick, future computing system designs will be constrained by power density and total system energy, and will require new programming models and implementation strategies. Data movement in the memory system and interconnect will dominate running time and energy costs, making communication cost reduction the primary optimization criterion for compilers and programmers:

In this talk I will describe some of the main techniques for reducing the impact of communication, starting with latency hiding techniques, including the use of one-sided communication in Partitioned Global Address Space languages. I will describe some of the performance benefits from overlapped and pipelined communication but also note cases where there is “too much of a good thing” that causes congestion in network internals. I will also discuss some of the open problems that arise from increasingly hierarchical computing systems, with multiple levels of memory spaces and communication layers.

Other Computing Sciences contributions to the symposium include a paper on “Distributed Merge Trees” by Dmitriy Morozov and Gunther Weber; and a poster on “Scaling Data Race Detection for Partitioned Global Address Space Programs” co-authored by Costin Iancu with Chang-Seo Park and Koushik Sen of UC Berkeley.

CS Researchers Among the Founding Editors of New ACM Journal

Kathy Yelick, Associate Lab Director for Computing Sciences, and Aydin Buluç, a member of the Complex Systems Group in CRD, are among the founding associate editors of the new ACM Transactions on Parallel Computing (TOPC). TOPC publishes novel and innovative work on all aspects of parallel computing, including foundational and theoretical aspects, systems, languages, architectures, tools, and applications. Submissions are now being accepted for the journal.

This Week’s Computing Sciences Seminars

Single Program, Multiple Data Programming for Hierarchical Computations

Tuesday, February 19, 10:00–11:00 am, 50B-2222
Amir Kamil, University of California, Berkeley

Large-scale parallel machines are programmed primarily with the single program, multiple data (SPMD) model of parallelism. This model combines independent threads of execution with global collective communication and synchronization operations. Previous work has demonstrated the advantages of SPMD over other models: its simplicity enables productive programming and avoids many classes of parallel errors, and at the same time it is easy to implement and amenable to compiler analysis and optimization. Its local-view execution model allows programmers to take advantage of data locality, resulting in good performance and scalability on large-scale machines. However, the model does not fit well with divide-and-conquer parallelism or hierarchical machines that mix shared and distributed memory. In this talk, I will introduce a hierarchical team mechanism that retains the performance, safety, and analysis advantages of SPMD parallelism while supporting hierarchical algorithms and machines. I will demonstrate how to ensure alignment of collective operations on teams, eliminating a significant class of deadlocks. I will also describe a hierarchical pointer analysis that can take into account both the hierarchical machine structure and user-defined hierarchical teams. Finally, I will present application case demonstrating the expressiveness and performance of the team mechanism. I will show that the model enables divide-and-conquer algorithms such as sorting to be elegantly expressed, and that team collective operations increase performance of a conjugate gradient benchmark by up to a factor of two. The model also facilitates optimizations for hierarchical machines, improving scalability of a particle in cell application by 8x, performance of sorting by up to 40%, and execution time of a stencil code by as much as 14%.

Reliable Iterative Condition-Number Estimation: Scientific Computing and Matrix Computations Seminar

Wednesday, February 20, 12:10–1:00 pm, 380 Soda Hall, UC Berkeley
Sivan Toledo, UC Berkeley

The talk will present a reliable Krylov-subspace method for estimating the spectral condition number of a matrix A. The main difficulty in estimating the condition number is the estimation of the smallest singular value \sigma_{\min} of A. Our method estimates this value by solving a consistent least-squares minimization problem with a known minimizer using a specific Krylov-subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a singular vector corresponding to \sigma_{\min}. Extensive experiments show that the method is very reliable. It is often much faster than a dense SVD and it can sometimes estimate the condition number when running a dense SVD would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR) and it works equally well on square and rectangular matrices.

DREAMS Tutorial: The Particle Filter

Wednesday, February 20, 2:10–4:00 pm, 490H Cory Hall, UC Berkeley
Thomas Schön, Linköping University

The particle filter provides a solution to the state inference problem in nonlinear dynamical systems. This problem is indeed interesting in its own right, but it also shows up as a sub-problem in many relevant areas, such as for example sensor fusion and nonlinear system identification. The aim of this tutorial is to provide you with sufficient knowledge about the particle filter to allow you to start implementing particle filters on your own.

We will start out by providing a brief introduction to probabilistic modeling of dynamical systems in order to be able to clearly define the nonlinear state inference problem under consideration. The next step is to briefly introduce two basic sampling methods, rejection sampling and importance sampling. The latter is then exploited to derive a first working particle filter. The particle filter can be interpreted as a particular member of a general class of algorithms referred to as sequential Monte Carlo (SMC). This relationship is explored in some detail in order to provide additional understanding.

The particle filtering theory has developed at an increasing rate over the last two decades and it is used more and more in solving various applied problems. During this tutorial I focus on the method and to some extent on the underlying theory. Hence, I will not show any real world examples, I save them for my seminar on Thursday, where I will show how the particle filter has been instrumental in solving various nontrivial localization problems.

Memristor: Past, Present, and Future

Friday, February 22, 2:00–3:00 pm, 390 Hearst Memorial Mining Building, UC Berkeley
Leon Chua, UC Berkeley, EECS

What is a memristor? Why did it take 37 years to make one? Why did HP’s memristor generate so much excitement? How does the memristor retain its memory even after the power is switched off? What is the difference between a non-volatile memristor and a locally-active memristor? How smart are they?

This lecture reminisces the conceptual genesis of the memristor in 1971 along with an in-depth circuit-theoretic characterization and generalizations.

In particular, pinched hysteresis loops will be identified as the universal fingerprint of memristive systems, thereby unifying a broad class of non-volatile memories based on resistance switchings, such as RRAMs, MRAMs, phase-change memories, etc., published over the past two decades, as memristors.

Future generalizations to memristor-based sysnapses and ion channels will also be delineated and proposed as the right stuff for building low-power, laptop size and adaptive brain-like computers that could outperform existing supercomputers in many tasks, e.g. face recognition and dynamic associative memory.

Link of the Week: Exploring Earth’s Dark Matter

In a recent issue of Nature, Janet Jansson of Berkeley Lab’s Earth Sciences Division explores whether omics can provide insights into microbial ecology in ways that cannot be achieved using traditional methods. Her editorial, “Exploring Earth’s Dark Matter,” asks whether modern “big data” technologies can be as revealing (or more so) than conventional experiments to study microbe–environment associations.

This question is particularly relevant to soil because of its high microbial diversity. For the past several years, Jansson has studied how the wealth of data from genomics, transcriptomics, proteomics, and metabolomics can provide insights into habitats. She asks, “Should major investments be made in big-data infrastructure to support the analysis of Earth’s microbial communities, similar to those afforded to astrophysics?”

About Computing Sciences at Berkeley Lab

The Lawrence Berkeley National Laboratory (Berkeley Lab) Computing Sciences organization provides the computing and networking resources and expertise critical to advancing the Department of Energy's research missions: developing new energy sources, improving energy efficiency, developing new materials and increasing our understanding of ourselves, our world and our universe.

ESnet, the Energy Sciences Network, provides the high-bandwidth, reliable connections that link scientists at 40 DOE research sites to each other and to experimental facilities and supercomputing centers around the country. The National Energy Research Scientific Computing Center (NERSC) powers the discoveries of 7,000-plus scientists at national laboratories and universities, including those at Berkeley Lab's Computational Research Division (CRD). CRD conducts research and development in mathematical modeling and simulation, algorithm design, data storage, management and analysis, computer system architecture and high-performance software implementation. NERSC and ESnet are Department of Energy Office of Science User Facilities.

Lawrence Berkeley National Laboratory addresses the world's most urgent scientific challenges by advancing sustainable energy, protecting human health, creating new materials, and revealing the origin and fate of the universe. Founded in 1931, Berkeley Lab's scientific expertise has been recognized with 13 Nobel prizes. The University of California manages Berkeley Lab for the DOE’s Office of Science.

DOE’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States, and is working to address some of the most pressing challenges of our time. For more information, please visit science.energy.gov.