CSC 254/454 Fall 2018

CSC 254/454 Fall 2018

Programming Language Design and Implementation

Course description and prerequisites

Policies for grading, attendance, and academic honesty (updated 8/27)

Teaching Staff and Office Hours: 

  • Prof. Chen Ding, Fridays 11am to 12pm in Wegmans Hall 3407, x51373.
  • Alan, 12pm-1pm Friday, Wegmans 2215
  • Alex, 11am-12 Thursday, Wegmans 3201
  • Jason, 12:30pm-1:30pm Tuesday, Hylan 301 (CS Minor’s Lab)
  • Jie, 2pm-4pm Tuesday, Wegmans 2311
  • Michael, 9am-10am Wednesday, Hylan 301 (CS Minor’s Lab)
  • Princeton, 12:45pm-1:45pm Wednesday, Hylan 301 (CS Minor’s Lab)
  • Wei, 4pm-6pm Tuesday, Wegmans 2602
  • Wentao, 3pm-5pm Wednesday, Wegmans 2207

Help Sessions

  • 5pm to 6pm Wednesday, Gavett 301
  • 3:30pm to 4:30pm Thursday, Wegmans 1009

Course Schedule and Handouts (online access at learn.rochester.edu > CSC 254 > Handouts)

The initial schedule can be accessed here.  See learn.rochester.edu for the most recent version.  Contact the instructor if you have problem accessing the site.

Grading (tentative):

  • attendance and pop quizzes, 10%
  • mid-term and final exam, 15% and 20% of the remaining 90%
  • assignments and projects, 65% of the remaining 90%

Textbooks

 Scott, M: Programming Language Pragmatics, 4th Edition

Other Materials

No Starch Press
April 2011, 400 pp.
ISBN-13: 978-1-59327-283-8

Web page for 2017 course taught by Prof. Scott.

Policies for CSC 2/454

The workload will be heavy.   Be sure to read instructions carefully, start the assignment early, know where/when to seek help, and work with peers.

For group projects, in most cases all students receive the same grade for the group.   Team membership may be self-selected or assigned.  If you prefer, there is a possibility to work alone.  Contact the TA in charge.

Grades will be released periodically to Blackboard, the University’s on-line course management system.  

Attendance and Class Participation

Class attendance is mandatory.  Please arrive on time.  I expect to start at 10:25 sharp, and late arrivals disturb the folks who are already there.   I also plan to start many classes with a quiz.

My goal is to spend class time answering questions and explaining material in ways that complement the text.  In other words, lecture should complement the text, not rehash it.  This means, of course, that  reading is mandatory, and must be completed before the corresponding lecture.  If no one has questions or suggested discussion topics, I will call on you—so be prepared!

As a general rule, if there’s something you don’t understand, make me stop and explain it.  There are probably a dozen people sitting around you who didn’t understand it either, but don’t have the nerve to say so.  Likewise, if I’m belaboring something that everyone understands, prod me to move on.

 Prof. Scott has made his lecture notes available on-line, but keep in mind that the exams may include topics covered in class, even if they are not in the text book or lecture notes. 

Project Help Sessions

 The time and location are fixed each week.  Attendance is voluntary.   There are two sessions each week covering the same topics, which will be given in announcements at the beginning of the week.

No Late Assignments

It is my strict policy not to accept late assignments.  Exceptions will be made only by the instructor.  Note, however, that I am extremely generous with partial credit, so turn in what you have.

Every semester I have students who let a due date pass.  When I ask them what happened they say “Oh, I didn’t finish, so I didn’t turn anything in.”  Then I have to give them a zero.  If they had turned in even some reasonable preliminary thoughts on how they might have done the assignment—without a single line of code—they often could have received as much as 30% of the total points.  This can easily make the difference between letter grades at the end of the semester.

So if it looks like you aren’t going to make a due date, don’t keep debugging down to the wire.  Stop an hour early and take the time to organize what you have and put together a write-up that presents it in the best possible light.  Your transcript will love you for it. 

Academic Honesty

Student conduct in CSC 2/454 is governed by the College Academic Honesty Policy, the Undergraduate Laboratory Policies of the Computer Science Department, and the University’s Acceptable Use Policy for Information Technology.  I helped to draft some of the descriptions.  I believe in them strongly, and will enforce them aggressively.

The following are details specific to CSC 2/454.

Exams and quizes in CSC 2/454 must be strictly individual work.

Collaboration on programming assignments among team members is of course expected.  Collaboration on assignments acrossteams is encouraged at the level of ideas.  Feel free to ask each other questions, brainstorm on algorithms, or work together at a whiteboard.  You may not claim work as your own, however, unless you transform the ideas into substance by yourself.  Among other things, this means that you must leave any brainstorming sessions with no written or electronic notes—only what you carry in your head.

If you use the work of others (e.g., you download a function from the web at the last minute so that you can get the rest of your project working), then (1) either you must have the author’s explicit permission or the material must be publicly available, and (2) you must label what you copied, clearly and prominently, when you hand it in.  You will of course get points only for the parts of your assignment that you wrote yourself.

To minimize the temptation to steal code, all students are expected to protect any directories or on-line repositories in which they do their work.

For purposes of this class, academic dishonesty is defined as

  • Any attempt to pass off work on an exam or quiz that didn’t come straight out of your own head.
  • Any collaboration on assignments beyond the sharing of ideas, unless the collaborating parties clearly and prominently explain exactly who did what, at turn-in time.
  • Any activity that has the effect of significantly impairing the ability of another student to learn.  Examples here might include destroying the work of others, interfering with their access to resources, or deliberately providing them with misleading information.

Note that grades in CSC 2/454 are assigned on the basis of individual merit rather than relative standing, so there is no benefit—even a dishonest one—to be gained by sabotaging the work of others.

I work under the assumption that students are honest.  I will not go looking for exceptions.  If I discover one, however, I will come down on it very hard.  Over the past few years, I have submitted about a dozen cases to the College Board on Academic Honesty.  All resulted in major penalties for the students involved.


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.

RTHMS: A tool for data placement on hybrid memory system

This paper uses a rule based algorithm to guide data placement on hybrid memory system. The hybrid memory system is abstracted as combinations of a FAST memory (HBM) and SLOW memory (DRAM). FAST memory is assumed to have larger bandwidth but larger latency than SLOW memory. Also FAST memory can be either software managed or be configured as the CACHE of SLOW memory. 

The placement decision problem is divided into two steps: (1) Each memory object will be first evaluated individually with a score for each placement choice (FAST, SLOW, CACHE). The rules are listed below(corresponding scores are in brackets):
      R1 (single threaded), memory objects accessed by only one thread are preferred to be placed in SLOW memory. (0, 0, 1). As the high bandwidth will be under utilized if placed in FAST.
      R2 (computing intensity), the number of computing operations on data fetched from memory is larger than a threshold. The memory objects are preferred to be placed in SLOW. (0,0,1). As long latency will be amortized by the cost of computing.
      R3 (small size), memory objects whose cache size is smaller than last level cache (LLC) size are preferred to be placed in SLOW. (0, 0, 1). As LLC can hold all the data and most accesses will result in accessing LLC.
      R4 (small/strided access), memory objects with regular access pattern are preferred to be placed in FAST. (1, 0, -1). As regular accesses are highly optimized to hide memory latency, the bandwidth is the bottleneck.
      R5 (good locality), memory objects with good locality but size larger than FAST memory are preferred to use CACHE model. (N/A, 1, 0)
      R6 (poor locality), memory objects with poor locality but size larger than FAST memory are preferred to be placed in SLOW. (N/A, -1, 1)
      R7 (irregular access, low concurrency), memory objects with irregular memory accesses but low concurrency are preferred to be placed in SLOW. (0, -1, 1). As irregular accesses is hard to optimize to hide latency and low concurrency can not amortize that, placing in lower latency memory is preferred.
      R8 (irregular access, high concurrency), memory objects with irregular memory accesses and high concurrency are preferred to be placed in FAST. (1, -1, 0). As high concurrency can amortize the latency well, exploring the benefit of higher bandwidth is preferred.
       The intuitions  behind can be summarized as follows: placing in FAST is to best utilizing the bandwidth, placing in SLOW is to best utilizing the small latency and place in CACHE is to best utilizing the locality.
       (2) But the size of FAST memory is limited, not every objects that prefer FAST can be all placed in FAST. Global decisions are made by assigning a rank for each object with the following 2 rules to identify which objects should be prioritized for FAST memory assignment.
       R9 (total access), memory objects that accessed often are typically important data structures. Memory objects with larger total accesses have higher priority.
       R10 (write intensity), memory objects that have larger write intensity are more likely to be benefited from higher bandwidth (FAST). Memory objects with larger write intensity have higher priority.