Hierarchical Pointer Analysis for Distributed Programs Amir Kamil

Hierarchical Pointer Analysis for Distributed Programs Amir Kamil

Hierarchical Pointer Analysis for Distributed Programs Amir Kamil U.C. Berkeley December 7, 2005 Hierarchical Pointer Analysis 1 Amir Kamil Background Titanium is a single program, multiple data (SPMD) dialect of Java All threads execute the same program text Designed for distributed machines Global address space all threads can access all memory At runtime, threads are grouped into processes A thread shares a physical address space with some other, but not all threads Hierarchical Pointer Analysis 2

Amir Kamil Memory Hierarchy Global memory is composed of a hierarchy Program Processes Threads 0 1 global tlocal 2 3 plocal Locations can be thread-local (tlocal), processlocal (plocal), or in another process (global) Hierarchical Pointer Analysis 3

Amir Kamil Goal Our goal is to produce a (flow-insensitive) pointer analysis that takes the memory hierarchy into account We define a small SPMD language based on Titanium We produce a type system that accounts for the memory hierarchy We give an overview of the abstract pointer analysis Hierarchical Pointer Analysis 4 Amir Kamil Language Syntax Types ::= int | refq Qualifiers q ::= tlocal | plocal | global (tlocal @ plocal @ global) Expressions e ::= newl (allocation)

| transmit e1 from e2 (communication) | e1 e 2 (dereferencing assignment) Hierarchical Pointer Analysis 5 Amir Kamil Type Rules Allocation The expression newl allocates space of type in local memory and returns a reference to the location The label l is unique for each allocation site and will be used by the pointer analysis The resulting reference is qualified with tlocal, since it references thread-local memory Thread 0 newl int tlocal Hierarchical Pointer Analysis ` newl : reftlocal 6

Amir Kamil Type Rules Communication The expression transmit e1 from e2 evaluates e1 on the thread given by e2 and retrieves the result If e1 has reference type, the result type must be widened to global Statically do not know source thread, so must assume it can be any thread ` e1 : ` e2 : int Thread 0 Thread 1 y transmit y from 1 ` transmit e1 from e2 : expand(, global) tlocal global Hierarchical Pointer Analysis expand(refq , q) reft(q, q)

expand(, q) otherwise 7 Amir Kamil Type Rules Dereferencing Assignment The expression e1 e2 puts the value of e2 into the location referenced by e1 (like *e1 = e2 in C) If e1 has type refplocal reftlocal , and e2 has type reftlocal , the assignment could be unsound ` e1 : refq ` e2 : robust(, q) Thread 0 y z tlocal Thread 1 ` e1 e2 : refq plocal plocal tlocal

robust(refq , q) false if q @ q robust(, q) true otherwise Hierarchical Pointer Analysis 8 Amir Kamil Pointer Analysis Since language is SPMD, analysis is only done for a single thread (assume thread 0) Each expression has a points-to set of abstract locations that it can reference Abstract locations also have points-to sets Abstract locations consist of label and qualifier A-loc (l, q) can refer to any concrete location allocated at label l and with type qualifier v q from thread 0 Thread 0 (l, tlocal) (l, plocal) Hierarchical Pointer Analysis newl int tlocal

9 Thread 1 newl int tlocal Amir Kamil Pointer Analysis Allocation and Communication The abstract semantics for allocation and communication are similar to the type rules An allocation newl produces a new abstract location (l, tlocal) The result of the expression transmit e1 from e2 is the global versions of the a-locs resulting from e1 e1 ! {(l1, tlocal), (l2, plocal), (l3, global)} transmit e1 from e2 ! {(l1, global), (l2, global), (l3, global)} Hierarchical Pointer Analysis 10 Amir Kamil

Pointer Analysis Dereferencing Assignment For assignment, must take into account actions of other threads Thread 0 x (l1, tlocal) Thread 1 x (l2, tlocal) y x ! {(l1, tlocal)}, (l1, plocal) x (l2, plocal) y

(l1, plocal) (l2, plocal) y x y : (l1, tlocal) ! (l2, plocal), (l1, plocal) ! (l2, plocal), y ! {(l2, plocal)} Hierarchical Pointer Analysis Thread 2 11 (l1, global) ! (l2, global) Amir Kamil Race Detection Results Static race detection in Titanium using pointer analysis + concurrency analysis Most are false positives, so lower is better Benchmark No Pointer Analysis

One-Level Analysis Two-Level Analysis gas 2482 779 223 gsrb 512 187 18 lu-fact 490 177

1 pps 7026 1827 26 spmv 443 177 0 Hierarchical Pointer Analysis 12 Amir Kamil

Recently Viewed Presentations

  • Globalization, Growth and Poverty David Dollar World Bank

    Globalization, Growth and Poverty David Dollar World Bank

    David Dollar World Bank June 2006 ... but will rise again if same growth as 1980-98 1820 1850 1890 1929 1870 1910 1950 Bourguigon and Morrisson Mean log derivation Poverty incidence has continued to decline in recent years The numbers...
  • The Biodiversity of Aquatic Invertebrates in Bayside Marina

    The Biodiversity of Aquatic Invertebrates in Bayside Marina

    The Biodiversity of Aquatic Invertebrates in . Bayside Marina and Fort Totten Park. Seohee Lee. 1, Seoyeong Lee. 1, Gabriella Ng. 1 & Jessica Cohen, Ph.D.
  • Graduation Requirements - Berkeley County School District

    Graduation Requirements - Berkeley County School District

    An Individual Graduation Plan is a road map that guides students toward their education, career and employment goals. Discuss high school graduation requirements.
  • COMP9321 Web Application EngineeringSemester 1, 2017

    COMP9321 Web Application EngineeringSemester 1, 2017

    So, What is Big Data? Big data refers to our ability to collect and analyse the ever expanding amounts of data and meta-data that we are generating every second!
  • Un viaje de vida - Ning

    Un viaje de vida - Ning

    La Luz respondió. La información transferida a mí fue que durante una experiencia de vida después de la muerte, tus creencias configuran el tipo de información que recibirás antes de la Luz. Si tú eras un budista o católico o...
  • VectorS & Relative Motion

    VectorS & Relative Motion

    Which of the following is a frame of reference for measuring motion? coordinate system . diagram . graph . none of the above . Question #18-22 Story. In a circus parade, a clown standing on a float moving at a...
  • Слайд 1 - cdn.gdz4you.com

    Слайд 1 - cdn.gdz4you.com

    Презентація. З біології. На тему: "Гіпотези виникнення життя" Учениці 7(11) Б класу
  • TORTORA  FUNKE  CASE ninth edition MICROBIOLOGY an introduction

    TORTORA FUNKE CASE ninth edition MICROBIOLOGY an introduction

    Adaptive immunity: Immunity, resistance to a specific pathogen. Host Defenses: OR WHAT WE ARE BORN WITH Figure 16.1 OR THE ABILITY TO MAKE THEM Physical Factors Skin Epidermis consists of tightly packed cells with Keratin, a protective protein Physical Factors...