Class Preparation Instructions

The success of this class largely depends on the quality of the in-class discussions. Therefore, I strongly suggest that you prepare for each discussion class by preparing a writeup according to the guideline below. The intent of these homework assignments is to promote discussion rather than test knowledge, and should hence be brief and consist mostly of discussion points. The writeups account for part of your final grade, and are due before the beginning of each class. Writeups will be graded within a week of submission. The grading policy is outlined at the end of this document.


Preparation Guideline

Class preparation should consist of reading the assigned material, and at a minimum, answering the 9 short questions below. Please treat these questions as a way of thinking about, and more importantly critiquing, the paper. I give example answers regarding speculative execution (branch prediction). The example answers contain a single (or maybe two) discussion point, but you should try to come up with more, especially if preparing the assignment in a group (strongly recommended). Please keep your answers to bullet points as much as possible, rather than complete paragraphs. Also, you may choose to rephrase some of the questions based on your understanding or opinions of the paper, the questions appear as a guideline. Some additional tips for reading a paper are at the bottom of this page.

1. What is the problem being solved?

This should not be a summary of the paper, but rather your interpretation of the main problem (or problems) being addressed. This is the sort of information that is ideally summarized in the beginning of the introduction and repeated in the conclusions (the two parts of the paper you should read first).

Increasingly deeper pipelines require more parallelism than is apparent in a sequential instruction stream.

2. Who are the intended users?

Please think of the type of user that the solution addresses. While you may also list what readers the paper targets (e.g., architects), please write down actual users of the system as well (not just users of the idea). Important things to think about are how narrow or broad is the problem and solution. Who faces this problem? Does everyone who faces the problem benefit from the solution?

While not explicit in the reading material, the users are implied to utilize a serial coding style, lack structured parallelism, or require backward compatibility.

3. What is unique about the suggested solution?

This basically means comparing the presented solution to prior and other work. If you are not familiar with other work, you may rely on the related-work comparisons in the paper. If you are familiar, or are interested, mention things not discussed by the authors.

By speculating on the direction of a branch before the result of the condition is executed, the hardware can discover pipeline parallelism without the need for explicitly parallel software. Without the suggested technique, software would be required to expose enough parallelism to fill the pipeline.

4. How is the idea evaluated?

Simulation of a processor with branch prediction on standard benchmarks, that were compiled without knowledge of the execution pipeline depth or width.

5. Was the evaluation in line with the stated user requirements?

Basically, did the presented evaluation convince you that the proposed solution addresses the problem that you identified in Q1 for the users you thought of in Q2. And if not, then why (critiquing other people’s work helps you improve your own).

Yes, the evaluation demonstrated that deep pipelines can be kept full by the processor, even when processing programs with no explicit parallelism.

6. Was technology a factor in the problem or solution?

In most cases the answer would be “yes”, but the reasons might be implied and not made explicit.

“Technology” refers to changes or advances in the underlying physical technology used. Mostly, what happens with VLSI and interconnects.

The authors did not specifically address technology, and it is not clear whether increasing pipeline depth is a result of technological constraints or pressure by users for increased core frequency and overall performance.

7. Were new tools or software techniques introduced?

No, speculative execution is a hardware-only technique.

8. How may users with other requirements be affected?

Here, again, please think of other types of users as in Q2. Try to come up with points that the paper did not address that may be particular relevant to certain type or groups of users.

Generally, speculative execution reduces the runtime of applications and should benefit many users. However, the hardware structures required to support it increase processor cost, area, and potentially power. These factors may be detrimental to use of speculative execution in the context of embedded applications that typically have significant data level parallelism, which can be utilized by explicitly parallel software and compilers.

9. How can the discussion of this paper be generalized in the context of the class?

The idea here is to think of the two main threads of this class: first, understanding what user requirements and system constraints are and how they affect one another in the paper; second, developing skills in designing experiments that can evaluate an idea and convince others of its utility with regard to specific problems and user requirements. This is a hard question to answer, but basically you can think of it as: (1) what did you get out of this paper, and (2) what you think I intended you to get out of the paper and discussion.

  • Hardware only technique that does not take advantage of potential software assistance and hints.
  • Technique may greatly benefit unstructured code such as that run by the OS and potentially just-in-time compilers and optimizers.

10. What other papers or material did you read to prepare? Were there any terms or concepts you did not fully grasp?

Other comments?

  • Branch prediction is key to enabling effective out-of-order superscalar processors, and can therefore also be discussed in comparison to VLIW architectures and compilers.
  • For a mobile user, does speculative execution increase or decrease battery life?


Submission Instructions

Please submit your writeup in email to mattan.erez@gmail.com. Writeup is strictly due before class starts (i.e., Mondays at 10:29am).

(:comment Please submit your writeup (one writeup per person) before class starts on Blackboard. If everyone submits a writeup it simplifies grading and feedback — please submit the same writeup for all members of the group (may re-evaluate this submission policy later). :)


Grading policy

These assignments are for the benefit of the class and, again, not for testing knowledge. Therefore, the grading will be roughly as follows:

  • A - if you demonstrated that you are well prepared for class, by showing that you read and thought about the paper in the broad context of the course.
  • A+ - if you did the above and also had discussion points that surprised us.
  • B - if you it looks like you read the paper but didn’t give it enough thought.
  • C - if it appears that you are not prepared but made some attempt.
  • F - if you did not submit anything and did not tell us why (before or after the class).

General Paper-Reading Tips

  1. Before diving in, think about what your goals are, and what you want to get out of the paper. You need to approach the reading with an aim to extract info; you may want to target specific areas of the paper in case you are looking for something particular. Keeping these objectives in hand will help you while reading.
  2. Read the abstract first. This should be an advertisement for the paper.
  3. Read the conclusions. Figure out what the authors accomplished, so you know

what their goals were.

  1. Find the “paper overview” section in the introduction and read it if you need to. If you don’t know about a certain topic, you may find background material here.
  2. Make a quick first pass through the paper, so you understand their presentation of the topics. Figure out how the equations fit into the discussion, but don’t try to understand the math. On the second pass, read the paper more carefully.
  3. Highlight important parts of a paragraph so you don’t have to reread the entire paragraph each time. This helps in class discussions as well.
  4. Write down an outline as you go- this will help you remember what you have read. You can refer back to this outline as you go through the paper.
  5. Look up key references if you are looking for a particular topic. This paper may not have what you are looking for, but it may build on top of a topic you need to research. In the library, you can find guides that list forward references for each paper, which may also be useful in your quest.