Uncategorized

August 22, 2018

CSC 253/453 Fall 2018

CSC 253/453 Fall 2018

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.  Yu Feng, 5pm to 6pm, Mondays and Wednesdays, Wegmans Hall 3407.   Patrick Ferner, 2:30pm to 3:30pm, Tuesdays, Wegmans 2215 (updated 9/11).

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

Grading:

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

Assignments are typically handed out on Wednesday and due the following Tuesday midnight.

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) pages 3 to 5 on the “essential difficulties” of software development and skim the rest of the paper.

“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

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.
Available through Carlson Library at: Internet

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/)

Learn You a Haskell for Great Good!
A Beginner’s Guide
by Miran Lipovača (http://learnyouahaskell.com)
No Starch Press, April 2011.

Programming Language Pragmatics, 4th Edition
Author: Scott, Michael L.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: CRL PersCpy

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

Topics:

See schedule

 

Policies for CSC 2/453

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

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 3:25 sharp, and late arrivals disturb the folks who are already there.    You are encourage to ask or answer questions in class.  I may call on you just to know what you think.  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.

I will assign reading before and after lectures.   Reading is mandatory  It includes all lecture slides released to Blackboard, and textbook chapters/sections listed on the first slide of each lecture.   Keep in mind that the exams include topics covered in class and in the required reading. 

Late Submission Policy

A student may have a total of two extra days in all assignments.  They can be used as either a one-day extension for two assignments, or a two-day extension for one assignment.  A student must inform the TA about the extension before the due time.  No other late submission is permitted.

Academic Honesty

Student conduct in CSC 2/453 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/453.

Exams in CSC 2/453 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/453 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.

August 20, 2018

Character Co-Occurrence in Shakespeare’s Sonnets and the Bible

Co-Occurrence Blog Cover

This past summer, I’ve had the pleasure of working with Professor Chen Ding, Lucinda Liu, and Professor Daniel Gildea on an all-timescale co-occurrence analysis algorithm for optimizing microprocessor storage usage. This analysis can efficiently provide co-occurrence ratios for multiple timescales, which are time allowed for or taken by a process or sequence of events. The timescale is used to determine the likelihood of two events occurring together within that time window, giving a co-occurrence ratio. The developed algorithm is unique in its ability to calculate co-occurrence ratios for multiple timescales more efficiently than a brute-force method.

An initial pass of a trace of objects stores the distance between different elements of the trace. These distances can be used to see where gaps between trace objects are to wide to fall in the same time window, giving us a count of absence windows. The beauty of this algorithm is that the expensive operation, the initial pass of the trace, only needs to be done once to calculate timescale analysis of all pairs in a trace. By counting absence windows, joint and single frequencies can be determined.

We define the co-occurrence ratio to be the joint frequency of the pair divided by the single frequency of a given element. The given element is known to be present in a time window, meaning that the co-occurrence ratio represents the probability of finding the other element in the same time window. This makes the co-occurrence ratio a conditional probability.

This analysis was initially intended for use in optimizing processor cache utilization, by placing frequently co-occurring memory objects together in memory. The precise explanation can be found this paper. However, this concept can be extrapolated to any trace, whether it be a trace of words, or music notes, or pixels in a photo.

We applied our algorithm to Shakespeare’s Sonnets and the King James Bible, treating each character as a memory access taking one unit of time, skipping symbols and spaces. The letters, ignoring capitalization, are treated as memory accesses. We used timescales of 2, 5, and 10 to look at adjacent pairs, what one hand can type, and what two hands can type. Below are links to the data files and analysis of Shakespeare’s Sonnets and the King James Bible for multiple timescales using our algorithm:

Shakespeare’s Sonnets Timescale 2 Timescale 5 Timescale 10
King James Bible Timescale 2 Timescale 5 Timescale 10

The data can be interpreted as the conditional probability of seeing the second character given the first character is present in a given time window. Each individual character appears the same number of windows as the timescale size. So, if a second character is always adjacent to the first character on the same side the maximum co-occurrence ratio should be (timescale – 1)⁄timescale. The reason for this is that there will be one window that includes the first character but not the second.

For example, the character ‘q’ should always precede the character ‘u’. So, given a time window with ‘q’ the probability seeing ‘u’ in the same window should be at least (timescale – 1)⁄timescale. This means that all pairs with a co-occurrence ratio above that value have the second character on both sides of the first character like in the case of all word containing the substring “eve”. This is why for a timescale of 2 in Shakespeare’s Sonnets the pair (q, u) can be beaten by pairs like (x, e), but with larger timescales u’s from other words boost the (q, u) co-occurrence to put it in the lead.

Co-Occurrence Diagram

An example from Shakespeare’s Fourth Sonnet. Note how with the pair (q, u) the first window contains ‘q’ but not ‘u’ while the other nine windows have both characters. Also, the ‘q’ present in this trace appears in the same number of windows as the timescale size.

It is important to note that this method of co-occurrence analysis is not tallying frequencies. So when the pair (q, u) has the highest co-occurrence ratio, it does not mean that is the most common pair. Since the character ‘q’ is rarely used in the English language, its single occurrences are low, while its joint occurrences with the character ‘u’ are high. This is why for all the tests above many of the pairs with the highest affinities are uncommon consonants paired with a much more common vowel, like ‘e’. In both texts where the timescale 10 analyses were used, the top 10 pairs, excluding (q, u), have the character ‘e’ as a second character.

The data collected through this analysis has numerous uses outside of literature. The co-occurrence information can be used to evaluate the querty keyboard layout, or be used in speech therapy. Both the texts used here are from the same era, the turn of the sixteenth century into the seventeenth. It is possible that the character co-occurrence ratios could change with modern text or transcribed speech. Other than analyzing text, this analysis can be applied to images or videos for facial or object recognition.

I hope that this interesting re-application of memory layout analysis was entertaining to read about and I’d like to thank Professor Chen Ding, Lucinda Liu, and Professor Daniel Gildea for working with me on this project.

Image Sources: https://upload.wikimedia.org/wikipedia/commons/f/f6/Sonnets1609titlepage.jpg
https://upload.wikimedia.org/wikipedia/commons/e/e8/King-James-Version-Bible-first-edition-title-page-1611.png

April 1, 2018

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 (HICSS–29), 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.

 

December 21, 2017

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.
October 21, 2017

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)

 

October 21, 2017

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”
June 15, 2017

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.