WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |

«Automatic Mapping of Real Time Radio Astronomy Signal Processing Pipelines onto Heterogeneous Clusters Terry Esther Filiba Electrical Engineering and ...»

-- [ Page 1 ] --

Automatic Mapping of Real Time Radio Astronomy

Signal Processing Pipelines onto Heterogeneous

Clusters

Terry Esther Filiba

Electrical Engineering and Computer Sciences

University of California at Berkeley

Technical Report No. UCB/EECS-2013-147

http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-147.html

August 15, 2013

Copyright © 2013, by the author(s).

All rights reserved.

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission.

Automatic Mapping of Real Time Radio Astronomy Signal Processing Pipelines onto Heterogeneous Clusters by Terry Esther Filiba A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Engineering – Electrical Engineering and Computer Sciences in the Graduate Division of the University of California, Berkeley

Committee in charge:

Professor John Wawrzynek, Co-chair Daniel Werthimer, Co-chair Professor Jan Rabaey Assistant Professor Aaron Parsons Fall 2013 Automatic Mapping of Real Time Radio Astronomy Signal Processing Pipelines onto Heterogeneous Clusters Copyright 2013 by Terry Esther Filiba Abstract Automatic Mapping of Real Time Radio Astronomy Signal Processing Pipelines onto Heterogeneous Clusters by Terry Esther Filiba Doctor of Philosophy in Engineering – Electrical Engineering and Computer Sciences University of California, Berkeley Professor John Wawrzynek, Co-chair Daniel Werthimer, Co-chair Traditional radio astronomy instrumentation relies on custom built designs, specialized for each science application. Traditional high performance computing (HPC) uses general purpose clusters and tools to parallelize the each algorithm across a cluster. In real time radio astronomy processing, a simple CPU/GPU cluster alone is insufficient to process the data. Instead, digitizing and initial processing of high bandwidth data received from a single antenna is often done in FPGA as it is infeasible to get the data into a single server.

Choosing which platform to use for different parts of an instrument is a growing challenge.

With instrument specifications and platforms constantly changing as technology progresses, the design space for these instruments is unstable and often unpredictable. Furthermore, the astronomers designing these instruments may not be technology experts, and assessing tradeoffs between different computing architectures, such as FPGAs, GPUs, and ASICs and determining how to partition an instrument can prove difficult. In this work, I present a tool called Optimal Rearrangement of Cluster-based Astronomy Signal Processing, or ORCAS, that automatically determines how to optimally partition an instrument across different types of hardware for radio astronomy based on a high level description of the instrument and a set of benchmarks.

In ORCAS, each function in a high level instrument gets profiled on different architectures. The architectural mapping is then done by an optimization technique called integer linear programming (ILP). The ILP takes the function models as well as the cost model as input and uses them to determine what architecture is best for every function in the instrument. ORCAS judges optimality based on a cost function and generates an instrument design that minimizes the total monetary cost, power utilization, or another user-defined cost.

i

–  –  –

Acknowledgments This work would not have been possible without the help of the people around me. I am very grateful to my co-advisor Dan Werthimer for his encouragement and mentorship throughout this process. I appreciate all the time and patience he put in to help me get to this point. I am also grateful to my co-advisor Professor John Wawrzynek for his guidance which helped motivate me and helped me develop my own research ideas. I would like to thank the members of my qual and dissertation committees, Professor Aaron Parsons, Professor Jan Rabaey, and Professor Geoff Bower for their time and help shaping this work. I also would like to thank Professor Don Backer for his wisdom and support. Although he is no longer with us, he made a lasting impact on my research and I am very grateful for that.

I also need to thank the members of my research group and my lab. Thanks to the members of CASPER and the BWRC, especially Mark Wagner, Jonathon Kocz, Peter McMahon, Henry Chen, Matt Dexter, Dave MacMahon, and Andrew Siemion. I appreciate the time everyone took teaching me, helping me debug things, and discussing my research.

Finally, I would like to thank the people who looked after me and brightened my time at UC Berkeley. Thanks to my parents and my sister Michelle for always being around whenever I needed them. I thank my boyfriend Ben Schrager and his family who welcomed me into their home and treated me like family. Thanks to my friends Sam Ezell, Rhonda Adato, Leslie Nishiyama, Olivia Nolan, Nat Wharton, Orly Perlstein and Ari Rabkin who kept reminding me that I would eventually finish. And, I am very grateful for the care I received from my allergist, Dr. James Kong, which made it possible for me to complete this work.





Chapter 1 Introduction Radio astronomers are trying to solve a very diverse set of problems. Asking questions such as “Are we alone,” and “When were the first stars and galaxies formed?” and researching galactic structure and formation, the nature of gravitational wave background, the transient universe, black holes, and extrasolar planets.

Naturally, this curiosity leads to the development of larger and higher bandwidth telescopes creating a flood of data. Keeping up with the data requires constant development of new instrumentation

1.1 Motivation

–  –  –

The diversity of problems and telescopes create a number of parameters an engineer needs to worry about while designing an instrument. The instrument be designed based on the algorithm required to process the data, the bandwidth of the data, the number of channels, and the list goes on. Figure 1.1 shows two pictures of two very different telescopes, the Very Large Array, or VLA, in Socorro, New Mexico and the Arecibo Telescope.

Traditionally, observatories dealt with this by designing custom instruments that would run on one telescope and solve one problem. This custom approach was the only way to get the requisite processing power to analyze the radio signals, but it resulted in costly designs, because the boards, backplanes, chips, protocols, and software all needed to be designed from scratch. To make matters worse, this approach resulted in a very long design cycle, requiring 5-10 years of development before an instrument could be deployed at a telescope and by the time the instrument was released, the hardware would be out of date.

Due to their custom implementations, these instruments also lacked flexibility. Each instrument was designed specifically for a single purpose. A hardware upgrade or algorithm modification would require a complete redesign of the instrument, and another long design cycle.

While these older designs needed to trade off flexibility for performance, newer technology can offer both performance and flexibility. Programmable devices such as FPGAs, GPUs and even CPUs can provide enough processing power to keep up with the data from many new telescopes. These devices make it easy to reprogram existing hardware to support newer algorithms, and, since they are programmed using portable languages, provide a quick path to upgrade hardware without redesigning the entire instrument.

With a huge range of technology available, choosing what hardware to use to build an instrument is a challenge. New technology, optimizations, and designs are constantly being developed and with everything constantly changing it’s difficult to know what is best.

1.2 Technological Challenges When building a large instrument, there is a wide variety of technology to choose from.

Unlike many applications, where the goal is to provide the fastest possible implementation, in real time radio astronomy instrumentation there is a performance target. Understanding the tradeoffs between different implementations is key to cost-effective design.

An instrument designed typically has four choices of hardware for their algorithm implementations. They can use CPUs, GPUs, FPGAs, and ASICs. Figure 1.2 shows each of these as a spectrum from general purpose to custom. The CPUs and, to a lesser extend GPUs, provide a very general purpose design experience, while FPGAs and ASICs require custom designs. This spectrum also can be used to generalize a number of other properties of the presented hardware. Platforms further right require higher design times and design complexity and provide less flexibility in the final design. And because the chips will be deployed in relatively low volume, the platforms on the right will also cost more money. The CHAPTER 1. INTRODUCTION

–  –  –

tradeoff is in power and performance. The platforms on the right provide higher performance and lower power consumption.

To better understand these tradeoffs, consider the two platforms in the center of the spectrum, the GPU and FPGA. NVIDIA GPUs can be programmed in CUDA. Its C-like structure makes it easy for CPU programmers to pick up and provides a lot of flexibility.

CUDA allows the programmer to use conditional and iterative programming the same way they would use C, easing the transition into GPU programming. FPGAs are programmed using a hardware description language, or HDL, which is less flexible and harder to learn than CUDA. In the FPGA computing model the data is streaming and everything is happening at the same time, requiring specialized programming. On the other hand, FPGAs offer an order of magnitude improvement in performance and power consumption. Each GPU requires hundreds of watts of power while an FPGA can be powered with tens of watts and a GPU can only process hundreds of megahertz of antenna data while an FPGA is capable of processing multiple gigahertz.

Although it may be easy to enumerate the differences between these platforms, understanding which is best is more difficult. In most cases, a heterogeneous approach is best. The best mix of platforms will ultimately depend on the desired instrument, available technology, as well as the price and power restrictions. This means that a brand new implementation must be designed for every new instrument.

Traditionally, designing an instrument can be a very long process. The astronomer will determine what type of instrument they want to build and what the specifications should be. The specification is handed off to a computer expert who will determine what platforms need to be used. The computer expert evaluates potential platforms. At best this may take a few hours if the computer expert is familiar with similar designs, but when working with newer technology or larger instruments this can take at least a week, possibly even months, giving the engineer time determine how to make the design fit. Any changes in the design will force the entire design process to iterate again, as was my experience developing part of a pulsar processor. To make matters worse, this process does not guarantee an optimal result.

The engineer may have a bias towards the technology she or he is familiar with. Benchmarks CHAPTER 1. INTRODUCTION for different technologies are very difficult to compare, as they represent different things, so the engineer might decide to simply check if it works on the preferred technology without testing alternate designs.

1.3 Optimal Rearrangement of Cluster-based Astronomy Signal Processing This dissertation explores an automated approach to instrument design using a tool called Optimal Rearrangement of Cluster-based Astronomy Signal Processing or ORCAS. The major contributions of this work are a toolflow that allows radio astronomy experts to design cost-optimal high performance instruments without the aid of a computer expert, the ability to quickly explore different designs in the algorithmic design space, and support for disparate benchmarks to find an optimal instrument design.

This tool provides cost-optimal mappings in a short amount of time. ORCAS allows the developer to define the instrument at a high level and a cost function defining some cost the developer is aiming to minimize. The cost function can represent something as simple as the price of the instrument or can be used to represent more complex parameters of the instrument such as design time.

ORCAS assesses the performance of different types of technologies in two ways. First, by using benchmarks of existing implementations of instrument building blocks such as FFTs and FIR filters we can directly assess the performance. Second, if a benchmark is not available, the tool can use a performance model instead, giving an estimate of how the block will perform. This makes it easy to keep up with improving technology and library performance without rewriting the entire tool every time a new library version or board is released.

We evaluate ORCAS by benchmarking existing libraries, such as CUFFT and the CASPER library, and use those benchmarks to produce mappings for 3 types of instruments. Each mapping is compared to existing implementations to understand how this automated approach compares to the old approach of hand optimized mapping.

The remainder of the dissertation is organized as follows. Chapter 2 provides a more in-depth look at the algorithms commonly used in radio astronomy and their applications.

Chapter 3 describes related work, done by myself and others, that preceded this work.

Chapter 4 presents a high level description of the tool and explains how the tool goes from a description of the instrument to a fully mapped algorithm. The algorithm used to map the instrument is fully specified in chapter 5. Chapter 6 describes three instrument case studies and compares them to existing instruments. And finally, in Chapter 7, I present my conclusions and some opportunities for future work.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |


Similar works:

«US Particle Physics: Scientific Opportunities A Strategic Plan for the Next Ten Years Report of the Particle Physics Project Prioritization Panel 29 May 2008 Three frontiers of research in particle physics form an interlocking framework that addresses fundamental questions about the laws of nature and the cosmos.US Particle Physics: Scientific Opportunities A Strategic Plan for the Next Ten Years Report of the Particle Physics Project Prioritization Panel 29 May 2008 i In November 2007, at the...»

«REAPPRAISING ASTROLOGICAL CONCEPTS, OLD AND NEW “It is absurd to believe that the starts can make a man.” -Paracelsus 1. Establishing Some Limitations of Astrology Of all sciences or systems of prognostication, prediction or prophecy, Astrology alone enjoys the unique and peculair advantage of employing a base in the future from which one may calculate a pattern of relationships to the present and the past. If we know anything at all of tomorrow, it is only that the Sun and his host,...»

«A New Universe to Discover A Guide to Careers in Astronomy Published by The American Astronomical Society What are Astronomy and Astrophysics? Ever since Galileo first turned his new-fangled one-inch “spyglass” on the moon in 1609, the popular image of the astronomer has been someone who peers through a telescope at the night sky. But astronomers virtually never put eye to lens these days. The main source of astronomical data is still photons (particles of light) from space, but the tools...»

«Chromospheric Anemone Jets as Evidence of Ubiquitous Reconnection Kazunari Shibata,1* Tahei Nakamura,1 Takuma Matsumoto,1 Kenichi Otsuji,1 Takenori J. Okamoto,1,2 Naoto Nishizuka,1 Tomoko Kawate,1 Hiroko Watanabe, 1 Shin'ichi Nagata,1 Satoru UeNo,1 Reizaburo Kitai,1 Satoshi Nozawa,3 Saku Tsuneta,2 Yoshinori Suematsu,2 Kiyoshi Ichimoto,2 Toshifumi Shimizu,4 Yukio Katsukawa,2 Theodore D. Tarbell,5 Thomas E. Berger, 5 Bruce W. Lites,6 Richard A. Shine,5 Alan M. Title5 Kwasan and Hida...»

«Summit on Cost in Higher Education Monday, Oct. 21, 2013 Federal Reserve Bank of Boston Speaker and Panelist Biographies Neal Abraham Neal Abraham is Five College Professor of Physics and the executive director of Five Colleges, Inc., one of the oldest and most successful higher education consortia in the U.S. (serving Amherst, Hampshire, Mount Holyoke and Smith colleges and the University of Massachusetts Amherst). Prior to assuming his current position in August 2009, he served for 11 years...»

«STAR FORMATION AND GALACTIC EVOLUTION RICHARD B. LARSON Yale Astronomy Department, Box 208101, New Haven, CT 06520-8101 1 Introduction: Basic Problems Galaxies are, in their observable constituents, basically large bound systems of stars and gas whose components interact continually with each other by the exchange of matter and energy. The interactions that occur between the stars and the gas, most fundamentally the continuing formation of new stars from the gas, cause the properties of...»

«MEGALITHIC SITES IN BRITAIN BY A. THOM Chapter 6. Circles and Rings Chapter 7. The Compound Rings Chapter 8. Megalithic Astronomy OXFORD AT THE CLARENDON PRESS [ 1971 ] CONTENTS 1. Introduction 1 2. Statistical Ideas 6 3. Astronomical Background 14 4. Mathematical Background 27 5. Megalithic Unit of Length 34 6. Circles and Rings 56 7. The Compound Rings 84 8. Megalithic Astronomy 92 9. The Calendar 107 10. Indications of Lunar Declinations 118 11. The Outer Hebrides 122 12. A Variety of Sites...»

«MEICAS Y CURANDER0S EN TALAGANTE PROGRAMA DE DESARROLLO LOCAL PARA GESTORES CULTURALES UNIVERSIDAD ARCIS SINDICATO DE FOLCLORISTAS DE CHILE María Angélica Ortiz CAstro AGRADECIMIENTOS Nuestros agradecimientos a la energía cósmica por poner en nuestro camino seres que abrieran los espacios necesarios para que esta tesina fuera concretada: 2 RESUMEN La Tesina como su nombre lo indica versa sobre las practicas de meicas y curanderos de Talagante y pretende presentarlas en su desarrollo a...»

«A L I V E LY E L E C T R O N I C C O M P E N D I U M O F R E S E A R C H, N E W S, R E S O U R C E S, A N D O P I N I O N Astronomy Education Review 2011, AER, 10, 010101-1, 10.3847/AER2010040 Astrology Beliefs among Undergraduate Students Hannah Sugarman Department of Astronomy, University of Arizona, Tucson, Arizona 85721 Chris Impey Department of Astronomy, University of Arizona, Tucson, Arizona 85721 Sanlyn Buxner Department of Astronomy, University of Arizona, Tucson, Arizona 85721...»

«BUILDING TERRESTRIAL PLANETS A. Morbidelli1, J.I. Lunine2, D.P. O’Brien3, S.N. Raymond4, K. J. Walsh5 1 Dep. Cassiopée, Universite’ de Nice-Sophia Antipolis, Observatoire de la Côte d'Azur, CNRS, B.P.4229, 06304 Nice Cedex 4, France; morby@oca.eu 2 Department of Astronomy, Cornell University, Ithaca, NY 14853, USA; jlunine@astro.cornell.edu 3 Planetary Science Institute, 1700 E. Fort Lowell, Tucson, AZ 85719, USA; obrien@psi.edu 4 Université de Bordeaux, Observatoire Aquitain des...»

«ACVA Journal 2:2 Page 3 Krishnamurti Padhdhati: A New System of Vedic Astrology T.R. Raghunath, Ph.D. Dr. Raghunath offers a lucid introduction to the one of the most exciting new developments in Jyotish. K.S. Krishnamurti (1908 1972) is one of the original and systematic astrological thinkers of India. Today, his astrological system, known as K.P. (Krishnamurti Padhdhati), has dedicated practitioners in different parts of India, but it is generally excluded from consideration in the mainstream...»

«Jahresbericht 2009 Mitteilungen der Astronomischen Gesellschaft 93 (2010), 101–118 Bochum Ruhr-Universität Bochum Institut für Theoretische Physik IV Weltraumund Astrophysik Universitätsstraße 150, 44780 Bochum Telefon: +49 (234) 32-22032, Telefax: +49 (234) 32-14177 E-Mail: rsch@tp4.ruhr-uni-bochum.de WWW: http://www.tp4.ruhr-uni-bochum.de 1 Personal und Ausstattung 1.1 Personalstand Professoren und Privatdozenten Prof. Dr. Julia Becker [-23779] (seit 1.6.2009), PD. Dr. Horst Fichtner...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.