Rocket Compiler Creator and Computer Science Professor Philip Sweany Dies

Screen Shot 2018-04-01 at 5.55.45 PM

Philip Hamilton Sweany, PhD, beloved husband, brother, professor, colleague, and friend, died March 29, 2018 of neuroendocrine cancer.

(https://m.facebook.com/margaret.falersweany/posts/10213796046167865)

Born May 31, 1949 in Seattle, WA, Phil graduated from Washington State University with BS in Zoology in 1972.  He worked in air pollution research for 10 years before returning back to WSU to study and received a BS in Computer Science in 1982.  Phil married Margaret FalerSweany (Peggi) on January 27, 1980.  He received  an MS in 1986 and a PhD in 1992 in Computer Science from Colorado State University at Fort Collins, CO .  Phil was a member of the computer science faculty at Michigan Tech University at Houghton, MI from 1991 to 2000,  Texas Instruments’ Research and Development group in Dallas from 2000 to 2003, computer science and engineering faculty at University of North Texas in Denton from 2003 until his death in 2018.

Phil was my primary advisor during my MS study at Michigan Technological University from August 1994 to May 1996.  I joined his Rocket Compiler research group as a research assistant almost immediately after I arrived at MTU from China.  The computer science department was small and friendly.  I still remember about half dozen faculty members and a dozen graduate students by name and face and recall vivid memories of the time.   I remember Phil being extremely humorous.  One couldn’t stop smiling and laughing while conversing with him.  Also shortly after my arrival, my wife Linlin quit her graduate study at Peking U, and we started our married life.  It was also the first time I heard about Internet, had my first email account (cding@cs.mtu.edu), and my first home page (viewable from anywhere in the world).

Phil’s research was compiling for instruction level parallelism.  He and Steve Carr (who later became my co-advisor) put me to study a technique called software pipelining.  Under their direction, I was exposed to research and developed several improvements.  Through the work, the problem I found hardest and most intriguing was predicting the cost of a memory access.  This problem was the seed that grew into my later work at Rice, which then led to the research, past and present, at Rochester.

Next year I attended my first conference, when Phil took the whole group on the road to Ann Arbor, Michigan to attend 28th MICRO, November 29 to December 1, 1995.   My first paper was published shortly after at 29th Annual Hawaii International Conference on System Sciences (HICSS29), January 3-6, 1996, Maui, Hawaii.  Phil asked the department secretary to book the trip and told me that “unfortunately” to get “reasonable” airfare, I have to stay at Maui for the whole week!  I remember being handed a thick stack of paper tickets (Houghton to Detroit to LA to Honolulu to Maui and back) and when there, stayed in the luxury Intercontinental hotel, with its miles of private white-sand beach.  He put me in charge of renting a car (since I arrived first), although I have never rented a car before.  Phil took Peggi and I to dinner in the first evening.  We toured the rain forest together on the last day.  In between I remember swimming in the ocean, locking the key in the car, taking a helicopter tour, and a number of other things I did for the first time.

My spoken English was so accented that it was indecipherable.  Phil sent me to get help from Scientific and Technical Communication in Peggi’s department.  After being tutored by a student named Lynn for both English pronunciation and writing, people began to understand what I was saying.

At MTU, there were just a handful of CS graduate students, and we had an active social life.   There were multiple parties each year at faculty houses (or beach houses).  Phil and Peggi hosted the Thanksgiving party in their house in Hancock.  Theirs was my first encounter with not just the turkey but its many sides.  Fellow graduate students organized movie nights in the winter and excursions in the fall.  We spent a lot of time chatting when we sat in office, with Phil, Steve and other faculty occasionally walking by.  I remember passing the written test at DMV (made just one mistake) after half hour crash course in the office.  At MTU, graduate students stayed at the university apartments on the side of a hill next to campus.  I was elected a student officer working with a committee selecting movies to run each month on the residential cable network.  There was also much happened together with other Chinese students, e.g. the annual winter extravaganza.  But in about two years when I graduated in 1996, I was thoroughly, properly, and happily Americanized.

My memories at MTU 22 years ago were among the fondest of the time when I was young and a student of Phil.  I wrote the following comment yesterday after hearing the news:

Phil is my role model — a pure hearted scientist and teacher with uncompromising dedication to his research and students.  I’m most fortunate to have him as my MS advisor and will continue to follow his example.  His legacy lives through me and my students.

 

CS 255/455 Spring 2018

CSC 255/455 Software Analysis and Improvement (Spring 2017)

Lecture slides, reading, later assignments, and other material will be distributed through Blackboard.


Assignments:


 Course description

With the increasing diversity and complexity of computers and their applications, the development of efficient, reliable software has become increasingly dependent on automatic support from compilers & other program analysis and translation tools. This course covers principal topics in understanding and transforming programs by the compiler and at run time. Specific techniques include data flow and dependence theories and analyses; type checking and program correctness, security, and verification; memory and cache management; static and dynamic program transformation; and performance analysis and modeling.

Course projects include the design and implementation of program analysis and improvement tools.  Meets jointly with CSC 255, an undergraduate-level course whose requirement includes a subset of topics and a simpler version of the project.

 Instructor and grading

Teaching staff: Chen Ding, Prof., Wegmans Hall Rm 3407, x51373;  Fangzhou Liu, Grad TA;  Zhizhou Zhang, Undergrad TA.

Lectures: Mondays and Wednesdays, 10:25am-11:40am, Hylan 202

Office hours: Ding, Fridays 11am to noon (and Mondays for any 15 minute period between 3:30pm and 5:30pm if pre-arranged).

TA Office hours: Zhizhou, Mondays 2 to 3pm, open area outside the elevator, third floor Wegmans Hall.  Jerry, Tuesdays 3 to 4pm, 3407 Wegmans Hall.

Grading (total 100%)

  • midterm and final exams are 15% and 20% respectively
  • the projects total to 40% (LVN 5%, LLVM trivial 5%, loop+index 10%, dep 10%, par 10%)
  • written assignments are 25% (trivial 1%; 4 assignments 6% each)

 Textbooks and other resources (on reserve at Carlson)

Optimizing Compilers for Modern Architectures (UR access through books24x7), Randy Allen and Ken Kennedy, Morgan Kaufmann Publishers, 2001. Chapters 1, 2, 3, 7, 8, 9, 10, 11. lecture notes from Ken Kennedy. On-line Errata

Engineering a Compiler, (2nd edition preferred, 1st okay), Keith D. Cooper and Linda Torczon, Morgan Kaufmann Publishers. Chapters 1, 8, 9, 10, 12 and 13 (both editions). lecture notes and additional reading from Keith Cooper. On-line Errata

Compilers: Principles, Techniques, and Tools (2nd edition), Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Pearson.

Static Single Assignment Book, Rastello et al. (in progress)

Introduction to Lattices and Order,  Davey and Priestley, Cambridge University Press.

2017 2nd URCSSA Alumni Summit

On Oct. 26, Dr. Chengliang Zhang, former graduate and now Staff Software Engineer at Google Seattle,  was invited by Chinese Student and Scholar Association (URCSSA) to speak at the second Alumni Summit titled Cloud | Big Data | AI.  The compiler group held a separate mini-symposium to present our research and had lunch with our esteemed graduate.

MEMSYS 2017

 

Three Walls by the Monday’s keynote speaker Peter Kogge, University of Notre Dame

 

Memory Equalizer for Lateral Management of Heterogeneous Memory
Chen Ding (University of Rochester), Chencheng Ye (Huazhong University of Science and Technology), Hai Jin (Huazhong University of Science and Technology)

 

Spirited Discussion

Memory Systems Problems and Solutions

• Chen Ding, University of Rochester
• David Donofrio, Berkeley Labs
• Scott Lloyd, LLNL
• Dave Resnick, Sandia
• Uzi Vishkin, University of Maryland


Sally McKee: on Chip Cache


David Wang keynote


Hotel accommodation and conference dinner (and investigation … of murder)

 

Joel Fest


From Lane: “On Labor Day (Sept. 4), URCS will host a day of talks by wonderful speakers … in honor of our wonderful colleague Joel I. Seiferas’s retirement.”

JS: “Good morning and welcome. As the ‘Joel’ of ‘JoelFest,’ I have asked to say a (very) few words of introduction.

I can’t take credit for today’s program of distinguished speakers (or the presence of other notable colleagues), but I am happy that my recent retirement can be the excuse for it. I hope everyone enjoys and is stimulated by what you hear today.

… 

Thanks for today are also due to all of the following:  …

  • the entire well-oiled machine of an organizing committee, including, in addition to Muthu and Lane, Prof. Daniel Stefankovic and my wife Diane, and of course our distinguished speakers, to be introduced individually. 

Anyway, the U. of R. is clearly a great place to retire from.

More significantly (but briefly), Rochester also has been a wonderful place to work since I came here in 1979:

  • Faculty, past and present, have always been collegial, generous, smart, eloquent, and a pleasure to work with.
  • Past and present staff has always been eager and successful in providing the best support for the department.
  • The graduate students, especially, have been enthusiastic participants in the community, even in learning experiences much broader than what they needed for their theses.
  • In later years, the growing undergraduate community has become an impressive part of the mix, with many remarkable gems emerging there as well.”

 Speakers at JoelFest (full details see http://www.cs.rochester.edu/~lane/=joelfest/)

  • Zvi Galil, the John P. Imlay Dean of Computing and Professor at Georgia Tech’s College of Computing, “Online Revolutions: From Stringology with Joel to Georgia Tech’s Highly Affordable Master Degree”
  • Shafi Goldwasser, the RSA Professor of Electrical Engineering and Computer Science at MIT, “Pseudo-determinism”
  • Jon Kleinberg, Tisch University Professor of Computer Science at Cornell University, “Social Dynamics and Mathematical Inevitability”
  • Muthuramakrishnan Venkitasubramaniam, Department of Computer Science, University of Rochester, “The Status of Zero-Knowledge Proofs”

CSC 253 Fall 2017

CSC 253/453 Dynamic Language & Software Development

Prerequisites: CSC 252 and CSC 254 are required for CSC 453 and recommended for CSC 253. Familiarity with a dynamic programming language such as Python is required for CSC 253.
Crosslisted: TCS 453 (same requirement as CSC 253)

This course studies dynamically-typed programming languages and modular software development. Topics include principles and practice of modular design, functional and object-oriented programming techniques, software engineering concepts, software correctness and reliability, programming tools, and design examples. Ruby is used as the main instruction language. The lessons complement those in traditional compilers and programming languages courses, which focus mainly on statically-typed languages and individual algorithms rather than system design. A significant portion of the assignment is a group project.

Teaching Staff and office hours:  Prof. Chen Ding, Fridays 11am to 12pm in Wegmans Hall 3407, x51373.  John Jacob, 1pm to 2, Tuesdays, in the corner next to Wegmans Hall 3409.  Zhizhou Zhang, 3:30pm to 4:30, Thursdays, Wegmans Hall 3407, x51373.

Grading:

  • mid-term and final exams, 15% each
  • two written homeworks, 5% each
  • assignments and projects, 60%

Preparation (before first class):

“No Silver Bullet — Essence and Accidents of Software Engineering” is a classic paper on software engineering written by Turing Award winner Fred Brooks in 1986.  Read the paper (available here if accessed inside the UR network) especially pages 3 to 5 on the “essential difficulties” of software development.

“A former member of the SD10 Panel on Computing in Support of Battle Management explains why he believes the ‘star wars’ effort will not achieve its stated goals.”  Read the paper (available here if accessed inside the UR network) pages 2 to 4 the section titled “Why software is unreliable.”  Which of the “essential difficulties” was Parnas discussing?

More background of this debate, detailed rationales and an illuminating discussion of the ethical issues can be found in another article of Parnas: “SDI: A Violation of Professional Responsibility”.  The article does not seem to have a free version online, but you can read it by borrowing the book “Software Fundamentals” (included as Chapter 27) from the textbook reserve for CSC 253/453 at the Carlson Library.  The lease is two hours.

Further material will be distributed through the Blackboard web site  for students who have registered.  Contact the instructor if you have problem accessing the site.

Textbooks (online access at learn.rochester.edu > CSC 253 > Reserves > Materials on Reserve in the Library):

Software fundamentals : collected papers by David L. Parnas
Author: Parnas, David Lorge.
Imprint: Boston : Addison-Wesley, 2001.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.754 .P365 2001

Programming Languages: Application and Interpretation (http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/)
Copyright © 2003-07, Shriram Krishnamurthi
(Also see Prof. Findler’s course EECS 321 at https://www.eecs.northwestern.edu/~robby/courses/)

Object-oriented Software Engineering
Author: Schach, Stephen R.
Imprint: New York : McGraw-Hill, c2008.
Available at school book store. On Reserve at: Carlson Library Reserve Desk 2nd Floor

Design patterns in Ruby [electronic resource]
Author: Olsen, Russ.
Imprint: Upper Saddle River, NJ : Addison-Wesley, c2008.
On Reserve at: Internet

 

Other Materials

Ruby under a microscope [electronic resource] : an illustrated guide to Ruby internals
Author: Shaughnessy, Pat.
Imprint: San Francisco : No Starch Press, [2014]
Available at school book store.  Also on Reserve at: Internet
Fundamentals of software engineering
Author: Ghezzi, Carlo.
Imprint: Upper Saddle River, N.J. : Prentice Hall, c2003.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.758 .G47 2003

PROGRAMMING LANGUAGE PRAGMATICS, 3rd ed
Author: Scott, Michael L.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: CRL PersCpy

 

Topics:

See schedule

 

Dan-Towsley model of cache sharing

At Rochester we have studied the Dan-Towsley model multiple times.  The description in their paper takes some effort to understand.  Here we put down additional explanation for anyone who is interested in this model.  The formulas included here are screen copies from the original paper.

In this problem, we have a collection of D fixed size items that share an LRU cache that can store B items. The D items are divided into k partitions.  Each partition has D_k items and is accessed with the probability alpha_k.  The access is assumed to be uniformly random within each partition.  This corresponds to the Independence Reference Model (IRM) of King in 1971.

The LRU cache can be viewed as a stack with most recently accessed item at the top and least recently accessed item at the bottom.  The cache state is defined by the content of these k positions.  In this formulation, the state of each position is the partition id of the data item it stores.

We emphasize the use of partition id,  For example for B=3, k=2, and D_1=2, a valid cache state may be (1, 1, 2), with both items of Partition 1 in the cache.  This state records only the partition id, not the specific data item.

The following formula gives the set S of all possible cache states:

 

Screen Shot 2017-06-15 at 5.19.36 PM

A valid state is a sequence of B positions with two constraints shown by the formula.  First, for each partition k, the number of items in the cache cannot be more than its total number of times.  Second, the total number from all partitions  equals to B.   Using the example B=3, k=2, and D_1=2 again, (1,1,1) would not be a valid state since it violates the first constraint of S.

King formulated the problem as a Markov Chain.  A Markov Chain has a set of states and transition probabilities between the states.  A common example is a drunkard’s walk.  Let there be a set of bars.   When leaving each bar, the drunkard has some probability to go to another bar.  As a Markov Chain, each bar is a state.  We are interested in computing the likelihood for each state.   If we choose a state to compute the likelihood, we call this the target state.  We use all the states that may transit into the target state.   We call these preceding states.  An equation can be constructed to show that the likelihood of the target state from the likelihood of preceding states and the transit probability from them to the target state.   For the drunkard, we compute the likelihood that he visits a particular bar, e.g. Starry Night.  The Starry Night is the target state.  Its likelihood depends on a nearby bar, e.g. Joe Bean, so we can use the likelihood of Joe Bean times the probability that the drunkard would go from Joe Bean to Starry Night.

In the following, the target state x=(x_1, x_2, …, x_B).  Its likelihood is computed from all possible preceding states.  The first line of the equation shows the transitions due to cache hits, and the next two lines (a product of each other) the transitions due to cache misses.

Screen Shot 2017-06-15 at 5.19.09 PM

It is understandably non-trivial to solve a Markov Chain problem with this many states and transitions.  King gave an exact solution which has a high computational complexity, exponential to D and B.

The Dan-Towsley model is an efficient approximation.  It consists of almost entirely the following two equations.  Eq. 2 is the key.  In Eq. 2, p_k(j) is the probability of a Partition-k item is stored at position j, and r_k(j-1) the probability that if the item at position j-1 moves to j, the probability that this item is from Partition k.  The Dan-Towsley model says that the two probabilities are equal.

The equation is recursive, since the two probabilities are used to compute each other.  b_k(j) is the occupancy of Partition-k at stack positions up to j.  It is computed from p_k(j).  This occupancy is used to compute the likelihood that the miss happens for a Partition-k item.  Eq. 2 computes r_k(j-1) by a ratio.  The denominator is the likelihood of an access at stack position below j-1.  This is a miss for B=j-1.  The ratio is the likelihood that the miss happens for a Partition-k data item.

Screen Shot 2017-06-15 at 5.20.03 PM

Eq. 2 is easily solvable by iterating starting from j=1 and p_k(1)=alpha_k.

More explanation is needed for Eq. 2.  In the text, the paper says that r_k(j-1) is the probability that if the item at position j-1 moves to j, the probability that this item is from Partition k.  In the equation, the ratio is likelihood that the miss happens for a Partition-k data item.  The two are related in a subtle way — both are required for the occupancy stays the same before and after the miss.

Xiaoming Gu was the first to study and implement the Dan-Towsley model at Rochester.  In 2008, he derived the distribution of reuse distance of random access, which corresponds to the solution of IRM for k=1.  He then found the Dan-Towsley model and verified it as an efficient and accurate solution for any k.

The Dan-Towsley model is a brilliant solution based on the cache occupancy.   Because of the IRM assumptions, the miss ratio can be computed from cache occupancy.   The general solution needs to consider locality.  The general problem is solved in recent years including the footprint based model developed at Rochester.   It is extremely interesting to compare and contrast the occupancy-based model of cache sharing and locality-based models.

Asit Dan, Donald F. Towsley:  An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152

King, W. F., “Analysis of Paging Algo- rithms,” In Proc. IFIP Congress, pages 485- 490, Ljublanjana, Yugoslavia, aug 1971.

 

Gu, Xiaoming, “Reuse Distance Distribution in Random Access“, TR930, Computer Science Dept., U. Rochester, January 2008.

Acknowledgement.  The explanation here is partly the result of discussion with Chencheng Ye and Rahman Lavaee.  Chencheng’s research is supported by an IBM CAS fellowship, and Rahman by NSF CCF-1629376.