Radix sort is an algorithm that works by sorting non-negative integers based on their digit relative to a given position based on the decimal system (unit, tenth, hundredth, etc.). To illustrate, consider the following set of numbers: [170, 45, 75, 90, 2, 802, 2, 66] Sorting the numbers relative to the unit digits yields: [{170, 90}, {2, 802, 2}, {45, 75}, {66}] If we repeat the procedure, but now relative to the tenth digits we get: [{2, 802, 2}, {45}, {66}, {170, 75}, {90}] Repeating the process one more time relative to the hundredth digits results in all numbers sorted. [{2, 2, 45, 66, 75, 90}, {170}, {802}] Sorting relative to a position of the decimal system can be done using an algorithm called counting sort, which is explained in detail next. Counting Sort Remember, counting sort works in relation to a positon on the decimal system. From now on, we will call that position index and we will use the following convention: 0 (unit), 1 (tenth), 2 (hundredth), etc. The counting sort algorithm can be broken into the following steps, which are based on the unit digit (index=0). Step 1: Count the Digits Counting sort starts by creating an array of counters for each of the digits (0-9). This array will count the number of times a digit (relative to the index position) appeared in the to-be-sorted array. count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 As an exercise, update count for the following array using index=0. [170, 45, 75, 90, 2, 802, 2, 66] You should get: count = [2, 0, 3, 0, 0, 2, 1, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Step 2: Accumulate the Counts The counts that we computed in the previous step is going to be used to determine how many spots need to be left for each digit when sorting the number in the array. But before we do that, we need to accumulate the counts so we would know how many spots to skip when placing the numbers in their correct location. After accumulating the counts, the (count) array should look like the following: count = [2, 0, 5, 0, 0, 7, 8, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Step 3: Sorting Sorting can be done by reading the elements of the data array from right-to-left and using count to find its location. This procedure will need an auxiliary array since it cannot be done in-place. Let’s call this auxiliary array aux. Pass 1 [170, 45, 75, 90, 2, 802, 2, *66*] count[6] is 8 => so 66 should be placed at position 7 (we subtract 1 because our arrays start at zero) aux = [ , , , , , , ,66] We then update the count since we placed one number in aux. count = [2, 0, 5, 0, 0, 7, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 2 [170, 45, 75, 90, 2, 802, *2*, 66] count[2] is 5 => so 2 should be placed at position 4 (we subtract 1 because our arrays start at zero) aux = [ , , , ,2, , ,66] We then update the count since we placed one more number in aux. count = [2, 0, 4, 0, 0, 7, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 3 [170, 45, 75, 90, 2, *802*, 2, 66] count[2] is 4 => so 802 should be placed at position 3 (we subtract 1 because our arrays start at zero) aux = [ , , ,802,2, , ,66] We then update the count since we placed one more number in aux. count = [2, 0, 3, 0, 0, 7, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 4 [170, 45, 75, 90, *2*, 802, 2, 66] count[2] is 3 => so 2 should be placed at position 2 (we subtract 1 because our arrays start at zero) aux = [ , ,2,802,2, , ,66] We then update the count since we placed one more number in aux. count = [2, 0, 2, 0, 0, 7, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 5 [170, 45, 75, *90*, 2, 802, 2, 66] count[0] is 2 => so 90 should be placed at position 1 (we subtract 1 because our arrays start at zero) aux = [ ,90,2,802,2, , ,66] We then update the count since we placed one more number in aux. count = [1, 0, 2, 0, 0, 7, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 6 [170, 45, *75*, 90, 2, 802, 2, 66] count[5] is 7 => so 75 should be placed at position 6 (we subtract 1 because our arrays start at zero) aux = [ ,90,2,802,2, ,75,66] We then update the count since we placed one more number in aux. count = [1, 0, 2, 0, 0, 6, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 7 [170, *45*, 75, 90, 2, 802, 2, 66] count[5] is 6 => so 45 should be placed at position 5 (we subtract 1 because our arrays start at zero) aux = [ ,90,2,802,2,45,75,66] We then update the count since we placed one more number in aux. count = [1, 0, 2, 0, 0, 5, 7, 0, 0, 0] digit = 0 1 2 3 4 5 6 7 8 9 Pass 8 [*170*, 45, 75, 90, 2, 802, 2, 66] count[0] is 1 => so 170 should be placed at position 0 (we subtract 1 because our arrays start at zero) aux = [170,90,2,802,2,45,75,66] Now that we explained how counting sort works, it is your turn to implement the algorithm, making sure you pass all tests before proceeding to the next section. Radix Sort As described above, you can run counting sort on each of the index positions from the least to most significant digits to sort an entire array. Finish the implementation and make sure all tests are cleared. In TO-DO 2a, to get the number of digits of a number you can try rounding up the logarithm (base 10) of the number. Note that it doesn’t work for 0 and 1. Submission Upload RadixSort.java on Canvas. Rubric +.5 for each test passed rounded up to 5
Circular linked lists are special types of linked lists where the last element (the tail node) points back to the first node (the head node). One application of circular lists is in task schedulers. Imagine a multitasking operating system (OS). Each task has a size (an estimate of how long it will take to run it) and a priority: 1 for low (gray), 2 for standard (green), and 3 for high (red). The OS iterates over its circular list of tasks, given each task a slice of its processing time. Low priority tasks will be given just one slice of time, while standard tasks will be given 2 slices of time, and finally, high priority tasks will be given 3 slices of time. The goal of this assignment is to have you finish the implementation of a circular list and use it to simulate an OS scheduler running tasks with different priorities. Different priority tasks running The Task Class A task has size > 0 and a priority (1, 2, or 3). Tasks can be dead or alive. Tasks are always created in the “alive” state. A task can be run for a slice of time. The effect of running a task is that its size is decremented by 1 unit. If after running a task size becomes zero, then its status is set to “dead”. The Circular Linked List Class Just like a standard linked list, a circular list is defined using a head node. However, the tail node of a circular linked list always points to the head node. This makes it easier to iterate indefinitely over a circular linked list, which makes perfect sense for its used in a task scheduler. The Task Scheduler Class Most of the code for this class is given to you. The only part left is the “run” method, which should use the circular linked list iterator. While iterating over the tasks, check if the task is dead first. If that’s the case, just ignore the task and move to the next one in the list. If the task is alive, run it a number of times based on its priority (1x for low, 2x for standard, and 3x for high). For a better visual effect, have the code sleep for 250ms and then call repaint every time a task runs. The snippet below shows how to have your code sleeps for 250ms. try { Thread.sleep(250); } catch (Exception ex) { } Submission Zip Task.java, CircularLinkedList.java, and TaskScheduler.java into a file named lab_04.zip. Then upload lab_04.zip to Canvas. Rubric +2 Task class +2 CircularLinkedList class +1 TaskScheduler class
In this activity you will implement a Fraction class, which is defined by two integers: the numerator and the denominator. The Fraction class has a parameterless constructor that sets both the numerator and denominator to one (Fraction.DEFAULT_VALUE). The Fraction class also defines two parameterized constructors: one that accepts a value for the numerator, setting the denominator to one (Fraction.DEFAULT_VALUE); and another one that allows the user to set both the numerator and denominator; however, if the informed denominator is zero, this constructor should set it to one instead (Fraction.DEFAULT_VALUE). The Fraction class also defines “getter†and “setter†methods. The setDenominator method should forbid the user from changing the Fraction’s denominator to zero. Do not throw an exception if the denominator is set to zero. Instead, just “do nothing.” Other methods defined in the Fraction class are: getValue returns the value of the fraction (as a floating-point value); in other words, this method returns the results of dividing its numerator by its denominator; isNegative returns true if the value of the fraction is less than zero; false otherwise; gcd is a helper method that returns the “Greatest Common Divisor†of the numerator and the denominator of the fraction object; simplify divides the fraction’s numerator and denominator by the gcd of the numbers; also, if the numerator is positive and the denominator is negative, this method switch signs between them; finally, if the numerator and the denominator are both negatives, this method cancels their signs, making them both positive; isProper returns true if the function is proper; false otherwise; a fraction is considered proper if the absolute value of its numerator is smaller than the absolute value of its denominator. Unit Testing There is a set of unit test cases for the Fraction class. All tests are defined in the class named FractionTest. As discussed in class, TDD (or TestDriven Development) encourages the development team to write all tests for a class before its actual implementation. Advocates of TDD believe that this approach leads to a more focused coding because it gives a specific goal to the developer, which is to PASS all tests. However, in order for TDD to be effective, the tests must be thorough. In other words, a good set of tests is one that captures and verifies all possible uses of your class.Submission Zip Fraction.java and FractionTest.java in a file named fraction.zip (this is the file that you need to upload on Canvas). Rubric +2 Fraction class +3 FractionTest class BONUS POINTS +1 toString override in Fraction using the format “N/D”, replacing N by the numerator and D by the denominator. +1 doc folder with the JavaDoc with the Fraction class documentation.
Instructions 2. Please upload your code as a jupyter notebook on Google Classrooom. Written work, if any, should be scanned as a pdf and then uploaded. You should preferably do your written work in the same jupyter notebook using markdown cells. 3. Please run your code and show the output by printing meaningful output statements. 4. Readability of code is a criterion for grading. So write code with ample comments. 5. You need the CVXPY package for the first two problems. Go and spend some time on www.cvxpy.org to familiarize yourself with the package and the syntax. Prisoners’ Dilemma as a Bargaining Problem The Prisoners’ Dilemma is a famous model for illustrating the conflict between social cooperation and self-interested behavior. Consider a two player Prisoners’ Dilemma in which the cooperative payoff possibilities are mathematically described by a polytope which is defined as the convex hull of the payoff vectors (4,4), (6,0), (0,6) and (0,0). Suppose we think of the Prisoners’ Dilemma as a bargaining situation where the disagreement point is d = (d1,d2). The notion of a disagreement point introduces a constraint that player i cannot get a payoff below her disagreement point payoff di. Whether or not you want to invest in understanding this model, you can always start your work taking as given that the feasible set F of payoff vectors (u1,u2) for the bargaining problem is mathematically described as u1 + 2u2 ≤ 12 2u1 + u2 ≤ 12 u1 ≥ d1, u2 ≥ d2 Problem 1 (5 points). (Linear optimization using CVXPY). Use the CVXPY package to do this problem. Suppose the disagreement point is given by d = (3.5,2). A weighted utilitarian criterion is defined as W(u1,u2) = θu1 + (1 − θ)u2 where θ ∈ [0,1] The weighted utilitarian solution of the bargaining problem, defined as max W(u1,u2) such that (u1,u2) ∈F u1,u2 Plot player 1’s utilitarian optimum u1(θ) as the weight θ varies in [0,1]. Problem 2. (8 points). (Convex optimization using CVXPY). Use the CVXPY package to do this problem. Suppose the disagreement point is given by d = (3.5,2). A Nash welfare criterion is defined as N(u1,u2) = log(u1 − d1) + log(u2 − d2) Find the Nash bargaining solution of the bargaining problem, defined as such that (u1,u2) ∈F (a) (4 points). In addition to displaying the Nash bargaining solution, display the primaloptimal value and the optimal dual variables for the constraints as well. (b) (4 points). (Comparative statics). Now fix the disagreement payoff of player 2 at d2 = 2. In the same figure, plot how both players’ payoffs in the Nash bargaining solution vary as the disagreement payoff d1 of player 1 varies over the interval [2,5]. Problem 3. (7 points). (Convex optimization using interior point algorithm). You cannot use the CVXPY package here. Please implement the algorithm. Suppose the disagreement point is given by d = (2,1). Solve Problem 2(a) by implementing the interior point algorithm that uses log barrier for inequality constraints. Display the following (i) initial t and final t (ii) Nash bargaining solution (iii) primal optimal value (Maximized Nash welfare) (iv) dual optimal variables for constraints (v) inequality constraint function values at the optimum
In this activity you will create unit tests for specialized solid classes: Cube, Pyramid, and Cylinder. You will also generate documentation for the classes that you will implement. Solid The Solid class is an abstract class that defines a method to compute the volume of a solid. Cube The Cube class extends Solid and overrides the volume method according to the formula below.Implement 2 constructors for the Cube class: one that takes the side of the cube (if the informed value is invalid, then it should default to Solid.DEFAULT_MEASURE); and another that sets its side to Solid.DEFAULT_MEASURE automatically. Make sure that your implementation passes all of the tests defined in CubeTest. When you are done, document your class using JavaDoc’s format. Pyramid Begin by writing PyramidTest first. When you are satisfied with your tests, write the Pyramid class implementation, similarly to what was done in Cube. For example, have the measures default to Solid.DEFAULT_MEASURE if the informed value is invalid. Also, write a constructor that creates a Pyramid using Solid.DEFAULT_MEASURE for length, width, and height.Cylinder Use a similar approach to implement the CylinderTest and Cylinder classes.
Instructions 2. Please upload your code as a jupyter notebook on Google Classrooom. Written work, if any, should be scanned as a pdf and then uploaded. You should preferably do your written work in the same jupyter notebook using markdown cells. 3. Please run your code and show the output by printing meaningful output statements. 4. Readability of code is a criterion for grading. So write code with ample comments. Problem 1 (5 points). (Taylor approximation) Consider the univariate function f(x) = x2 + logx Suppose we want to approximate the function values in the vicinity of x = 1 using Taylor polynomials. Lets call the linear approximation function (linear Taylor polynomial) as L(x) and the quadratic approximation function (quadratic Taylor polynomial) as Q(x). (a) Plot f(x), L(x) and Q(x) in the interval [0,2] in the same graph. (b) Let the error associated with the linear approximation be given by eL(x) = f(x)−L(x), and the error associated with the quadratic approximation be given by eQ(x) = f(x)−Q(x). Plot and in the interval [0,2] in the same graph. 1 Problem 2 (6 points). (Combination descent algorithm) Write a code to compute the unconstrained minimum of the following optimization problem by implementing a combination descent algorithm with initial point (1,1).Problem 3 (9 points). (Combination descent algorithm) Suppose S is a subset of Rn that is defined by a collection of inequalities: S = {x∈Rn : for every j = 1,…,m, gj(x) ≥ 0} Associated with any such set S is the potential function defined asThe analytic center of the set S is the vector that minimizes the associated potential function i.e. the vector x that solves min Ψ(x) x As an example instance, suppose S is a subset of R2 described as above by three linear inequalities given by g1(x1,x2) = 2×2 − x1 g2(x1,x2) = 2×1 − x2 g3(x1,x2) = 1 − x1 − x2 Frame the problem as an unconstrained optimization problem and write a code that uses the combination descent algorithm with initial point (0.25,0.25) to compute the analytic center of S. (Hint: Since log is a monotonically increasing function, minimizing logf(x) is equivalent to minimizing f(x)) 2
Setup Clone this repository: git clone https://github.gatech.edu/omscs6601/assignment_4.git You will be able to use numpy, math, time and collections.Counter for the assignment You will be able to use the sklearn and graphviz for jupyter notebook visualization only No other external libraries are allowed for solving this problem. We do check. Please use the ai_env environment from previous assignments If you are using an IDE: Ensure that in your preferences, that ai_env is your interpreter and that the assignment_4 directory is in your project structure Else: From your ai_env Terminal: conda activate ai_env The supplementary testing notebooks use jupyter: visualize_tree and unit_testing. From your ai_env Terminal: jupyter notebook The supplementary Helper notebook to visualize Decision tree, requires the graphviz library. From your ai_env Terminal: pip install graphviz==0.17.0 or alternatively pip install -r requirements.txt If you have difficulty or errors on graphviz0.17 From your ai_env Terminal: conda install -c conda-forge python-graphviz which installs version 0.19 (compatible) Overview Machine Learning is a subfield of AI, and Decision Trees are a type of Supervised Machine Learning. In supervised learning an agent will observe sample input and output and learn a function that maps the input to output. The function is the hypothesis ”’ y = f(x)”’. To test the hypothesis we give the agent a test set different than the training set. A hypothesis generalizes well if it correctly predicts the y value. If the value is finite, the problem is a classification problem, if it is a real number it is considered a regression problem. When classification problems have exactly two values (+,-) it is Boolean classification. When there are more than two values it is called Multi-class classification. Decision trees are relatively simple but highly successful types of supervised learners. Decision trees take a vector of attribute values as input and return a decision. [Russell, Norvig, AIMA 3rd Ed. Chptr. 18] Decision Trees The deliverable for the assignment is to upload a completed **_submission.py_** to Gradescope. * All functions must be completed in **_submission.py_** for full credit **Important**: Submissions to Gradescope are rate limited for this assignment. **You can submit two submissions every 60 minutes during the duration of the assignment**. Since we want to see you innovate and imagine new ways to do this, we know this can also cause you to fail (spectacularly in my case) For that reason you will be able to select your strongest submission to Gradescope. In your Gradescope submission history, you will be able to mark your best submission as ‘Active’. This is a students responsibility and not faculty. ### The Files You are only required to edit and submit **_submission.py_**, but there are a number of important files: 1. **_submission.py_**: Where you will build your decision tree, confusion matrix, performance metrics, forests, and do the vectorization warm up. 2. **_decision_trees_submission_tests.py_**: Sample tests to validate your trees, learning, and vectorization locally. 3. **_visualize_tree.ipnb_**: Helper Notebook to help you understand decision trees of various sizes and complexity 4. **_unit_testing.ipynb_**: Helper Notebook to run through tests sequentially along with the readme ### Resources * Canvas *Thad’s Videos*: [Lesson 7, Machine Learning] (https://gatech.instructure.com/courses/225196/modules/items/2197076) * Textbook:Artificial Intelligence Modern Approach * Chapter 18 Learning from Examples * Chapter 20 Learning Probabilistic Models * [Cross-validation](https://en.wikipedia.org/wiki/Crossvalidation_(statistics)) * [K-Fold Cross-validation](http://statweb.stanford.edu/~tibs/sta306bfiles/cvwrong.pdf) ### Decision Tree Datasets 1. **_hand_binary.csv_**: 4 features, 8 examples, binary classification (last column) 2. **_hand_multi.csv_**: 4 features, 12 examples, 3 classes, multi-class classification (last column) 3. **_simple_binary.csv_**: 5 features, 100 examples, binary classification (last column) 4. **_simple_multi.csv_**: 6 features, 100 examples, 3 classes, multi-class classification (last column) 5. **_mod_complex_binary.csv_**: 7 features, 1600 examples, binary classification (last column) 6. **_mod_complex_multi.csv_**: 10 features, 2400 examples, 5 classes, multi-class classification (last column) 7. **_complex_binary.csv_**: 10 features, 2800 examples, binary classification (last column) 8. **_complex_multi.csv_**: 16 features, 4800 examples, 9 classes, multi-class classification (last column) 9. **_part23_data.csv_**: 4 features, 1372 example, binary classification (last column) * Not provided, but will have less class separation and more centroids per class. Complex sets given for development * **_challenge_binary.csv_**: 10 features, 5400 examples, binary classification (last column) * **_challenge_multi.csv_**: 16 features, 10800 examples, 9 classes, multi-class classification (last column) #### NOTE: path to the datasets! ‘./data/your_file_name.csv’ #### Warmup Data **_vectorize.csv_**: data used during the vectorization warmup for Assignment 4 #### Imports **NOTE:** We are only allowing four imports: numpy, math, collections.Counter and time. We will be checking to see if any other libraries are used. You are not allowed to use any outside libraries especially for part 4 (challenge). Please remember that you should not change add or change any input parameters other than in part 4. #### Rounding **NOTE:** Although your local tests will have some rounding, it is meant to quickly test your work. Overall this assignment follows the CI 6601 norm of rounding to 6 digits. If in doubt, in use round: “` x = 0.12345678 round(x, 6) Out[4]: 0.123457 “` — ### Part 0: Vectorization! _[10 pts]_ * File to use to benchmark tests: `vectorized_flatten()` 4. `vectorized_glue()` 5. `vectorized_mask()` — ## The Assignment [Creative Commons sourced][cc] E. Thadeus Starner5th is the 5th incarnation of the great innovator and legendary pioneer of Starner Eradicatus Mosquitoes. For centuries the mosquito has imparted only harm on human health, aiding in transmission of malaria, dengue, Zika, chikungunya, CoVid, and countless other diseases impact millions of people and animals every year. The Starner Eradicatus, *Anopheles Stephensi* laser zapper has obtained the highest level of precision, recall, and accuracy in the industry![Creative Commons sourced][cc] The secret is the classification engine which has compiled an unmatched library of classification data collected from 153 countries. Flying insects from the tiny Dicopomorpha echmepterygis (Parasitic Wasp) to the giant titanus giganteus (Titan Beetle) are carefully catalogued in a comprehensive digital record and indexed to support fast and correct classification. This painstaking attention to detail was ordered by A. Thadeus1st to address a tumultuous backlash from the International Pollinators Association to a high mortality among beneficial pollinators.[Creative Commons sourced][cc][Creative Commons sourced][cc] Skeeter explains his idea to E.T. to generalize the Starner Eradicatus zapper to handle a variety of these pests. Wonderful! E.T. exclaims, and becomes wildly excited at the opportunity to bring such an important benefit to the World.[Creative Commons sources below][cc] The wheels of invention lit up the research Scrum that morning as E.T. and Skeeter storyboard the solution. People are calling out all the adjustments, wing acoustics, laser power and duration, going through xyz positioning, angular velocity and acceleration calculations, speed, occlusion noise and tracking errors. You as the lead DT software engineer are taking it all in, when you realize and speak up…, sir… Sir… SIR… and a hush falls. Sir, we are doing Boolean classification and will need to refactor to multi-class classification. E.T. turns to you and with that look in his eye, gives you and your team two weeks to deliver multi-class classification! You will build, train and test decision tree models to perform multi-class classification tasks. You will learn how decision trees and random forests work. This will help you develop an intuition for how and why accuracy differs for training and testing data based on different parameters. ### Assignment Introduction For this assignment we need an explicit way to make structured decisions. The `DecisionNode` class will be used to represent a decision node as some atomic choice in a multi-class decision graph. You must use this implementation for the nodes of the Decision Tree for this assignment to pass the tests and receive credit. An object of type ‘DecisionNode’ can represent a * decision node * *left*: will point to less than or equal values of the split value, type DecisionNode, True evaluations * *right*: will point to greater than values of the split value, type DecisionNode, False evaluations * *decision_function*: evaluates an attribute’s value and maps each vector to a descendant * *class_label*: None * leaf node * *left*: None * *right*: None * *decision_function*: None * *class_label*: A leaf node’s class value * Note that in this representation ‘True’ values for a decision take us to the left. — ### Part 1: Building a Binary Tree by Hand #### Part 1a: Build a Tree _[10 Pts]_ In `build_decision_tree()`, construct a decision tree capable of predicting the class (col y) of each example. Using the columns A0-A3 build the decision tree and nodes in python to classify the data with 100% accuracy. Your tests should use as few attributes as possible, break ties with equal select attributes by selecting the one which classifies the greatest number of examples correctly. For ties in number of attributes and correct classifications use the lower index numbers (e.g. select **A1** over **A2**) | X | A0 | A1 | A2 | A3 | y | | — | ——- | ——- | ——- | ——- | — | | x01 | 1.1125 | -0.0274 | -0.0234 | 1.3081 | 1 | | x02 | 0.0852 | 1.2190 | -0.7848 | -0.7603 | 2 | | x03 | -1.1357 | 0.5843 | -0.3195 | 0.8563 | 0 | | x04 | 0.9767 | 0.8422 | 0.2276 | 0.1197 | 1 | | x05 | 0.8904 | -1.7606 | 0.3619 | -0.8276 | 0 | | x06 | 2.3822 | -0.3122 | -2.0307 | -0.5065 | 2 | | x07 | 0.7194 | -0.4061 | -0.7045 | -0.0731 | 2 | | x08 | -2.9350 | 0.7810 | -2.5421 | 3.0142 | 0 | | x09 | 2.4343 | -1.5380 | -2.7953 | 0.3862 | 2 | | x10 | 0.8096 | -0.2601 | 0.5556 | 0.6288 | 1 | | x11 | 0.8577 | -0.2217 | -0.6973 | -0.1095 | 1 | | x12 | 0.0568 | 0.0696 | 1.1153 | -1.1753 | 0 | #### Requirements: The total number of elements(nodes, leaves) in your tree should be < 10 #### Hints: To get started, it might help to **draw out the tree by hand** with each attribute representing a node. To create a decision function for `DecisionNode`, you are allowed to use python lambda expressions: “` func = lambda feature : feature[2] = 60% * 25 pts: average test accuracy over 10 rounds should be >= 75% Meanwhile back in the lab… As the size of our flying training set grows, it rapidly becomes impractical to build multiclass trees by hand. We need to add a class with member functions to manage this, it is too much! To do list: * Initialize the class with useful variables and assignments * Fill out the member function that will fit the data to the tree, using build * Fill out the build function * Fill out the classify function For starters, consider these helpful hints for the construction of a decision tree from a given set of examples: 1. Watch your base cases: 1. If all input vectors have the same class, return a leaf node with the appropriate class label. 2. If a specified depth limit is reached, return a leaf labeled with the most frequent class. 3. Splits producing 0, 1 length vectors 4. Splits producing less or equivalent information 5. Division by zero 2. Use the DecisionNode class 3. For each attribute alpha: evaluate the information gained by splitting on the attribute `alpha`. 4. Let `alpha_best` be the attribute value with the highest information gain. 5. As you progress in this assignment this is going to be tested against larger and more complex datasets, think about how it will affect your identification and selection of values to test. 6. Create a decision node that splits on `alpha_best` and split the data and classes by this value. 7. When splitting a dataset and classes, they must stay synchronized, do not orphan or shift the indexes independently 8. Use recursion to build your tree, by using the split lists, remember true goes left using decide 9. Your features and classify should be in numpy arrays where for dataset of size (_m_ x _n_) the features would be (_m_ x _n_-1) and classify would be (_m_ x _1_) 10. The features are real numbers, you will need to split based on a threshold. Consider different approaches for what this threshold might be. First, in the `DecisionTree.__build_tree__()` method implement the above algorithm. Next, in `DecisionTree.classify()`, write a function to produce classifications for a list of features once your decision tree has been built. How grading works: 1. We load **_mod_complex_multi.csv_** and create our cross-validation training and test set with a `k=10` folds. We use our own `generate_k_folds()` method. 2. We fit the (folded) training data onto the tree then classify the (folded) testing data with the tree. 3. We check the accuracy of your results versus the true results and we return the average of this over k=10 iterations. #### Functions to complete in the `RandomForest.fit()` to fit the decision tree as we describe above, and fill in `RandomForest.classify()` to classify a given list of examples. You can use your decision tree implementation or create another. Your features and classify should use numpy arrays datasets of (_m_ x _n_) features of (_m_ x _n_-1) and classify of (_n_ x _1_). To test, we will be using a forest with 80 trees, with a depth limit of 5, example subsample rate of 0.3 and attribute subsample rate of 0.3 How grading works: 1. Similar to 2b but with the call to Random Forest. #### Functions to complete in the `RandomForest` class: 1. `fit()` 2. `classify()` — #### Part 4 (Optional) Boosting Competition Challenge (Extra Credit) #### Let the games begin! — 让游æˆå¼€å§‹ — ας ξεκινήσει το παιχνίδι #### THIS WILL REQUIRE A SEPARATE SUBMISSION * Files to use: **_complex_binary.csv, complex_multi.csv_** * Allowed use of numpy, collections.Counter, and math.log * Allowed to write additional functions to improve your score * Allowed to switch to Entropy and splitting entropy * Ranked by Balanced Accuracy Weighted, Precision, and Recall * Ties broken by efficiency (speed) * Extra Credit Points towards your final grade: * 5 pts: 1st place algorithm test over 10 rounds * 4 pts: 2nd place algorithm test over 10 rounds * 3 pts: 3rd place algorithm test over 10 rounds * 2 pts: 4th place algorithm test over 10 rounds * 1 pt: 5th place algorithm test over 10 rounds Decision boundaries drawn by decision trees are very sharp, and fitting a decision tree of unbounded depth to a set of training examples almost inevitably leads to overfitting. In an attempt to decrease the variance of your classifier you are going to use a technique called ‘Boosting’ implementing one of the boosting algorithms such as, Ada-, Gradient- and XG-, boost or your personal favorite. Similar to RF, the Decision stumps are short decision trees used in these Ensemble classification methods * They are usually short (depth limited) * They use smaller (but more of them) random datasets for training with sampling bias * They use a subset of attributes sampled from the training set * They fit the tree to the sampled dataset and are considered specialized to the set * They use weighting of their sampling and classifiers to reflect the balance or unbalance of the data * They use majority voting (every tree in the forest votes) to classify a sample Ada-boost Algorithm example [Zhu, et al.]: N Samples, M classifiers, W weights, C classifications, K classes, I indicator 1. Initialize the observation weights wi = 1/n, i = 1, 2, . . . , n. 2. For m = 1 to M: 1. Fit a classifier T(m)(x) to the training data using weights wi. 2. Compute err(m) = Sum(i=1..n)wi I(ci != T(m)(xi)) / Sum(i=1..n) wi 3. Compute α(m) = log (1−err(m)/err(m)) + log(K − 1). 4. Set wi ↠wi · exp (α(m) I(ci != T(m)(xi)), i = 1, . . . , n. 5. Re-normalize wi. 3. Output C(x) = argmax(k) sum(m=1..M) α(m) · I(T(m)(x) = k). [Multi-class AdaBoost](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.4221&rep=rep1&type=pdf) Zhu, Ji & Rosset, Saharon & Zou, Hui & Hastie, Trevor. (2006). Multi-class AdaBoost. Statistics and its interface. 2. 10.4310/SII.2009.v2.n3.a8. When sampling attributes you choose from the entire set of attributes without replacement based on the weighted distribution. Notice that you favor or bias towards misclassified samples, which improves your overall accuracy. Visualize how the short trees balance classification bias. Complete `ChallengeClassifier.fit()` to fit the decision tree as we describe above, and fill in `ChallengeClassifier.classify()` to classify examples. Use your decision tree implementation as your classifier or create another. Your features and classify should use numpy arrays datasets of (_m_ x _n_) features of (_m_ x _n_-1) and classes of (_m_ x _1_). How grading works: To test, we will be running 10 rounds, using your boosting with 200 trees, with a depth limit of 3, example subsample rate of 0.1 and attribute subsample rate of 0.2. You will have a time limit. #### Functions to complete in the `ChallengeClassifier` class: 1. `init()` 2. `fit()` 3. `classify()` — ### Part 5: Return Your name! _[1 pts]_ Return your name from the function `return_your_name()` — ### Helper Notebook #### Note: You do not need to implement anything in this notebook. This part is not graded, so you can skip this part if you wish to. This notebook is just for your understanding purpose. It will help you visualize Decision trees on the dataset provided to you. The notebook Visualize_tree.iypnb can be use to visualize tree on the datasets. Things you can Observe: 1. How the values are split? 2. What is the gini value at leaf nodes? 3. What does internal nodes represents in this DT? 4. Why all leaf nodes are not at same depth? Feel free to change and experiment with this notebook. you can look and use Information gain as well instead of gini to see how the DT built based on that. ### Video and picture attribution [cc]: All GT OMSCS materials are copyrighted and retain rights prohibiting redistribution or alteration Creative Commons sources share and share alike were used for the videos: Thomas Bresson, CC BY 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Traumatic-insemination-and-female-counteradaptation-in-Strepsiptera-(Insecta)-srep25052-s2.ogv Peinert M, Wipfler B, Jetschke G, Kleinteich T, Gorb S, Beutel R, Pohl H, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Broscus_cephalotes.webm О.Ð.П., CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Termites_walking_on_the_floor_of_Eastern_Himalyan_rainforest.webm Jenis Patel, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:The_carrot_caterpillar_-.webm Contributor NamesPathé frères (France)Pathé Frères (U.S.)AFI/Nichol (Donald) Collection (Library of Congress)Created / PublishedUnited States : Pathé Frères, 1911., Public domain, via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Gaeana_calling.webm Shyamal, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Kluse_- _Tenebrio_molitor_larvae_eating_iceberg_lettuce_leaf_v_02_ies.webm Frank Vincentz, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Lispe_tentaculata_male_-_2012-05-31.ogv Pristurus, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Xylotrupes_socrates_(Siamese_rhinoceros_beetle)_behavior.webm Basile Morin, CC BY-SA 4.0 , via Wikimedia Commons laser – https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_2.webm https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_3.webm https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_4.webm Matthew D. Keller et al., CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Laser-induced-mortality-of-Anophelesstephensi-mosquitoes-srep20936-s5.ogv Keller M, Leahy D, Norton B, Johanson T, Mullen E, Marvit M, Makagon A, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Predicting-Ancestral-Segmentation-Phenotypes-from-Drosophila-to-Anopheles-Using-In-SilicoEvolution-pgen.1006052.s001.ogv Rothschild J, Tsimiklis P, Siggia E, François P, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Focused_Laguerre-Gaussian_beam.webm Jack Kingsley-Smith, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:President_Reagan%27s_Remarks_at_Bowling_Green_State_University,_September_26,_1984.webm Reagan Library, CC BY 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:NID_Participants_Preparing_Their_Project_- _Workshop_On_Design_And_Development_Of_Digital_Experiencing_Exhibits_-_NCSM_-_Kolkata_2018-08-09_3141.ogv Biswarup Ganguly, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Davos_2017__An_Insight,_An_Idea_with_Sergey_Brin.webm World Economic Forum, CC BY 3.0 , via Wikimedia Commons Creative Commons Attribution-Share Alike 4.0
In this assignment, you will work with probabilistic models known as Bayesian networks to efficiently calculate the answer to probability questions concerning discrete random variables. Resources You will find the following resources helpful for this assignment. Canvas Videos: Textbook: Chapter 13: Quantifying Uncertainty Chapter 14: Probabilistic Reasoning Others: Markov Chain Monte Carlo Gibbs Sampling Metropolis Hastings Sampling – 1 Setup 1. Clone the project repository from Github git clone https://github.gatech.edu/omscs6601/assignment_3.git 1. Navigate to assignment_3/ directory 2. Activate the environment you created during Assignment 0 conda activate ai_env In case you used a different environment name, to list of all environments you have on your machine you can run conda env list. 3. Run the following command in the command line to install and update the required packages pip install torch===1.4.0 torchvision===0.5.0 -f https://download.pytorch.org/whl/torch_stable.html pip install –upgrade -r requirements.txt Submission Please include all of your own code for submission in submission.py. Important: There is a TOTAL submission limit of 5 on Gradescope for this assignment. This means you can submit a maximum of 5 times during the duration of the assignment. Please use your submissions carefully and do not submit until you have thoroughly tested your code locally. If you’re at 4 submissions, use your fifth and last submission wisely. The submission marked as ‘Active’ in Gradescope will be the submission counted towards your grade. Restrictions You are not allowed to use following set of modules from ‘pgmpy’ Library. pgmpy.sampling.* pgmpy.factor.* pgmpy.estimators.* Part 1 Bayesian network tutorial: [35 points total] To start, design a basic probabilistic model for the following system: There’s a nuclear power plant in which an alarm is supposed to ring when the gauge reading exceeds a fixed threshold. The gauge reading is based on the actual temperature, and for simplicity, we assume that the temperature is represented as either high or normal. However, the alarm is sometimes faulty. The temperature gauge can also fail, with the chance of failing greater when the temperature is high. You will test your implementation at the end of each section. 1a: Casting the net [10 points] Assume that the following statements about the system are true: 1. The temperature gauge reads the correct temperature with 95% probability when it is not faulty and 20% probability when it is faulty. For simplicity, say that the gauge’s “true” value corresponds with its “hot” reading and “false” with its “normal” reading, so the gauge would have a 95% chance of returning “true” when the temperature is hot and it is not faulty. 2. The alarm is faulty 15% of the time. 3. The temperature is hot (call this “true”) 20% of the time. 4. When the temperature is hot, the gauge is faulty 80% of the time. Otherwise, the gauge is faulty 5% of the time. 5. The alarm responds correctly to the gauge 55% of the time when the alarm is faulty, and it responds correctly to the gauge 90% of the time when the alarm is not faulty. For instance, when it is faulty, the alarm sounds 55% of the time that the gauge is “hot” and remains silent 55% of the time that the gauge is “normal.” Use the following name attributes: “alarm” node: Represents the probability that an alarm system will be going off or not. “faulty alarm” node: Represents the probability that the alarm system is broken or not “gauge”: Represents the probability that the gauge will show either “above the threshold” or “below the threshold” (high = True, normal = False) “faulty gauge”: Represents the probability that the gauge is broken “temperature”: Represents the probability that the temperature is HOT or NOT HOT (high = True, normal = False) Use the description of the model above to design a Bayesian network for this model. The pgmpy package is used to represent nodes and conditional probability arcs connecting nodes. Don’t worry about the probabilities for now. Use the functions below to create the net. You will write your code in submission.py. Fill in the function make_power_plant_net() The following commands will create a BayesNet instance add node with name “alarm”: BayesNet = BayesianModel() BayesNet.add_node(“alarm”) You will use BayesNet.add_edge() to connect nodes. For example, to connect the alarm and temperature nodes that you’ve already made (i.e. assuming that temperature affects the alarm probability): Use function BayesNet.add_edge(,) BayesNet.add_edge(“temperature”,”alarm”) After you have implemented make_power_plant_net(), you can run the following test in the command line to make sure your network is set up correctly. python probability_tests.py ProbabilityTests.test_network_setup 1b: Setting the probabilities [15 points] Now set the conditional probabilities for the necessary variables on the network you just built. Fill in the function set_probability() Using pgmpy’s factors.discrete.TabularCPD class: if you wanted to set the distribution for node ‘A’ with two possible values, where P(A) to 70% true, 30% false, you would invoke the following commands: cpd_a = TabularCPD(‘A’, 2, values=[[0.3], [0.7]]) If you wanted to set the distribution for P(A|G) to be | G |P(A=true given G)| | —— | —– | | T | 0.75| | F | 0.85| you would invoke: cpd_ag = TabularCPD(‘A’, 2, values=[[0.15, 0.25], [ 0.85, 0.75]], evidence=[‘G’], evidence_card=[2]) Reference for the function: https://pgmpy.org/_modules/pgmpy/factors/discrete/CPD.html Modeling a three-variable relationship is a bit trickier. If you wanted to set the following distribution for P(A|G,T) to be | G | T |P(A=true given G and T)| | — | — |:—-:| |T|T|0.15| |T|F|0.6| |F|T|0.2| |F|F|0.1| you would invoke cpd_agt = TabularCPD(‘A’, 2, values=[[0.9, 0.8, 0.4, 0.85], [0.1, 0.2, 0.6, 0.15]], evidence=[‘G’, ‘T’], evidence_card=[2, 2]) The key is to remember that first entry represents the probability for P(A==False), and second entry represents P(A==true). Add Tabular conditional probability distributions to the bayesian model instance by using following command. bayes_net.add_cpds(cpd_a, cpd_ag, cpd_agt) You can check your probability distributions in the command line with python probability_tests.py ProbabilityTests.test_probability_setup 1c: Probability calculations : Perform inference [10 points] To finish up, you’re going to perform inference on the network to calculate the following probabilities: the marginal probability that the alarm sounds the marginal probability that the gauge shows “hot” the probability that the temperature is actually hot, given that the alarm sounds and the alarm and gauge are both working You’ll fill out the “get_prob” functions to calculate the probabilities: – get_alarm_prob() – get_gauge_prob() – get_temperature_prob() Here’s an example of how to do inference for the marginal probability of the “faulty alarm” node being True (assuming bayes_net is your network): solver = VariableElimination(bayes_net) marginal_prob = solver.query(variables=[‘faulty alarm’], joint=False) prob = marginal_prob[‘faulty alarm’].values To compute the conditional probability, set the evidence variables before computing the marginal as seen below (here we’re computing P(‘A’ = false | ‘B’ = true, ‘C’ = False)): solver = VariableElimination(bayes_net) conditional_prob = solver.query(variables=[‘A’],evidence={‘B’:1,’C’:0}, joint=False) prob = conditional_prob[‘A’].values NOTE: marginal_prob and conditional_prob return two probabilities corresponding to [False, True] case. You must index into the correct position in prob to obtain the particular probability value you are looking for. Part 2: Sampling [65 points total] For the main exercise, consider the following scenario. There are three frisbee teams who play each other: the Airheads, the Buffoons, and the Clods (A, B and C for short). Each match is between two teams, and each team can either win, lose, or draw in a match. Each team has a fixed but unknown skill level, represented as an integer from 0 to 3. The outcome of each match is probabilistically proportional to the difference in skill level between the teams. Sampling is a method for ESTIMATING a probability distribution when it is prohibitively expensive (even for inference!) to completely compute the distribution. Here, we want to estimate the outcome of the matches, given prior knowledge of previous matches. Rather than using inference, we will do so by sampling the network using two Markov Chain Monte Carlo models: Gibbs sampling (2c) and Metropolis-Hastings (2d). 2a: Build the network. [10 points] For the first sub-part, consider a network with 3 teams : the Airheads, the Buffoons, and the Clods (A, B and C for short). 3 total matches are played. Build a Bayes Net to represent the three teams and their influences on the match outcomes. Fill in the function get_game_network() Assume the following variable conventions: | variable name | description| |———|:——:| |A| A’s skill level| |B | B’s skill level| |C | C’s skill level| |AvB | the outcome of A vs. B (0 = A wins, 1 = B wins, 2 = tie)| |BvC | the outcome of B vs. C (0 = B wins, 1 = C wins, 2 = tie)| |CvA | the outcome of C vs. A (0 = C wins, 1 = A wins, 2 = tie)| Use the following name attributes: “A” “B” “C” “AvB” “BvC” “CvA” Assume that each team has the following prior distribution of skill levels: |skill level|P(skill level)| |—-|:—-:| |0|0.15| |1|0.45| |2|0.30| |3|0.10| In addition, assume that the differences in skill levels correspond to the following probabilities of winning: | skill difference (T2 – T1) | T1 wins | T2 wins| Tie | |————|———-|—|:——–:| |0|0.10|0.10|0.80| |1|0.20|0.60|0.20| |2|0.15|0.75|0.10| |3|0.05|0.90|0.05| You can check your network implementation in the command line with python probability_tests.py ProbabilityTests.test_games_network 2b: Calculate posterior distribution for the 3rd match. [5 points] Suppose that you know the following outcome of two of the three games: A beats B and A draws with C. Calculate the posterior distribution for the outcome of the BvC match in calculate_posterior(). Use the VariableElimination provided to perform inference. You can check your posteriors in the command line with python probability_tests.py ProbabilityTests.test_posterior NOTE: In the following sections, we’ll be arriving at the same values by using sampling. Hints Regarding sampling for Part 2c, 2d, and 2e Hint 1: In both Metropolis-Hastings and Gibbs sampling, you’ll need access to each node’s probability distribution and nodes. You can access these by calling: A_cpd = bayes_net.get_cpds(‘A’) team_table = A_cpd.values AvB_cpd = bayes_net.get_cpds(“AvB”) match_table = AvB_cpd.values Hint 2: While performing sampling, you will have to generate your initial sample by sampling uniformly at random an outcome for each nonevidence variable and by keeping the outcome of your evidence variables (AvB and CvA) fixed. Hint 3: You’ll also want to use the random package, e.g. random.randint() or random.choice(), for the probabilistic choices that sampling makes. Hint 4: In order to count the sample states later on, you’ll want to make sure the sample that you return is hashable. One way to do this is by returning the sample as a tuple. 2c: Gibbs sampling [15 points] Implement the Gibbs sampling algorithm, which is a special case of Metropolis-Hastings. You’ll do this in Gibbs_sampler(), which takes a Bayesian network and initial state value as a parameter and returns a sample state drawn from the network’s distribution. In case of Gibbs, the returned state differs from the input state at at-most one variable (randomly chosen). The method should just consist of a single iteration of the algorithm. If an initial value is not given (initial state is None or and empty list), default to a state chosen uniformly at random from the possible states. Note: DO NOT USE the given inference engines or pgmpy samplers to run the sampling method, since the whole point of sampling is to calculate marginals without running inference. “YOU WILL SCORE 0 POINTS ON THIS ASSIGNMENT IF YOU USE THE GIVEN INFERENCE ENGINES FOR THIS PART” 2d: Metropolis-Hastings sampling [15 points] Now you will implement the independent Metropolis-Hastings sampling algorithm in MH_sampler(), which is another method for estimating a probability distribution. The general idea of MH is to build an approximation of a latent probability distribution by repeatedly generating a “candidate” value for each sample vector comprising of the random variables in the system, and then probabilistically accepting or rejecting the candidate value based on an underlying acceptance function. Unlike Gibbs, in case of MH, the returned state can differ from the initial state at more than one variable. This slide deck provides a nice intro. This method should just perform a single iteration of the algorithm. If an initial value is not given, default to a state chosen uniformly at random from the possible states. Note: DO NOT USE the given inference engines to run the sampling method, since the whole point of sampling is to calculate marginals without running inference. “YOU WILL SCORE 0 POINTS IF YOU USE THE PROVIDED INFERENCE ENGINES, OR ANY OTHER SAMPLING METHOD” 2e: Comparing sampling methods [19 points] Now we are ready for the moment of truth. Given the same outcomes as in 2b, A beats B and A draws with C, you should now estimate the likelihood of different outcomes for the third match by running Gibbs sampling until it converges to a stationary distribution. We’ll say that the sampler has converged when, for “N” successive iterations, the difference in expected outcome for the 3rd match differs from the previous estimated outcome by less than “delta”. N is a positive integer, delta goes from (0,1). For the most stationary convergence, delta should be very small. N could typically take values like 10,20,…,100 or even more. Use the functions from 2c and 2d to measure how many iterations it takes for Gibbs and MH to converge to a stationary distribution over the posterior. See for yourself how close (or not) this stable distribution is to what the Inference Engine returned in 2b. And if not, try tuning those parameters(N and delta). (You might find the concept of “burn-in” period useful). You can choose any N and delta (with the bounds above), as long as the convergence criterion is eventually met. For the purpose of this assignment, we’d recommend using a delta approximately equal to 0.001 and N at least as big as 10. Repeat this experiment for Metropolis-Hastings sampling. Fill in the function compare_sampling() to perform your experiments Which algorithm converges more quickly? By approximately what factor? For instance, if Metropolis-Hastings takes twice as many iterations to converge as Gibbs sampling, you’d say that Gibbs converged faster by a factor of 2. Fill in sampling_question() to answer both parts. 2f: Return your name [1 point] A simple task to wind down the assignment. Return your name from the function aptly called return_your_name().
This assignment will cover some of the concepts discussed in the Adversarial Search lectures. You will be implementing game playing agents for a variant of the game Isolation. Table of Contents Get repository Setup Jupyter Jupyter Tips IDE Get repository Pull this repository to your local machine: git clone https://github.gatech.edu/omscs6601/assignment_2.git Setup Activate the environment: conda activate ai_env In case you used a different environment name, to list of all environments you have on your machine you can run conda env list. Install additional package that will be used to for visualising the game board. pip install ipywidgets==7.5.0 Jupyter Further instructions are provided in the notebook.ipynb. Run: jupyter notebook Once started you can access http://localhost:8888 in your browser. Jupyter Tips 1. My Jupyter notebook does not seem to be starting up or my kernel is not starting correctly. Ans: This probably has to do with activating virtual environments. If you followed the setup instructions exactly, then you should activate your conda environment using conda activate from the Anaconda Prompt and start Jupyter Notebook from there. 2. I was running cell xxx when I opened up my notebook again and something or the other seems to have broken. Ans: This is one thing that is very different between IDEs like PyCharm and Jupyter Notebook. In Jupyter, every time you open a notebook, you should run all the cells that a cell depends on before running that cell. This goes for cells that are out of order too (if cell 5 depends on values set in cell 4 and 6, you need to run 4 and 6 before 5). Using the “Run All” command and its variants (found in the “Cell” dropdown menu above) should help you when you’re in a situation like this. 3. The value of a variable in one of my cells is not what I expected it to be? What could have happened? IDE In case you are willing to use IDE (e.g. Pycharm) to implement your assignment in .py file. Please run: bash python helpers/notebook2script.py submission You will get autogenerated submission/submission.py file where you can write your code. However, make sure you have gone through the instructions in the notebook.ipynb at least once.
This assignment is designed to help you prepare your local python environment, introduce you to jupyter notebooks and provide a refresher on python language. After following this README you will have a python environment ready and will be able to proceed with learning about jupyter notebooks in the notebook.ipynb (where you will make your first graded submission!). Let’s get started! Table of Contents Get repository Conda Environment Packages Jupyter Summary Get repository First things first, let’s pull this repository to your local machine: git clone https://github.gatech.edu/omscs6601/assignment_0.git Then come back to this README to continue with further setup. Instructions to create a private forked repository for assignments The assignments you would be working on throughout this semester will potentially require multiple revisions. A good way to track these revisions is by using your own private repo to backup your assignments at various stages of completion. Please remember that your assignment repository should be private and only accessible to yourself so that you do not accidentally violate the OSI policy. You can use the following steps to create a private repository for assignment 0. Please replace the A0 url with the future assignments’ URL to repeat this for the future assignments. Get the class repo git clone –bare https://github.gatech.edu/omscs6601/assignment_0.git Mirror this to your private repo cd assignment_0.git git push –mirror https://github.gatech.edu/your_gatech_id/YOUR_REPO You can now delete the assignment_0.git directory cloned two steps ago if you wish. Now clone your private repo on your local system git clone https://github.gatech.edu/your_gatech_id/YOUR_REPO Next cd YOUR_REPO git remote add upstream https://github.gatech.edu/omscs6601/assignment_0.git You check if the remote branch has been added using git remote -v Now you can use it like this it will default to the origin (your repo) If you are scared of pushing to upstream you can disable pushing to upstream using git remote set-url –push upstream PUSH_DISABLED CondaConda is an open source package and environment management system. Conda quickly installs, runs and updates packages/libraries and easily creates, saves, loads, and switches between environments on your local computer. Please download Miniconda and install it on your local machine. Although we require Python 3.7 for this course, you should install the version of Miniconda for any Python 3 version (e.g. Python 3.x). You can override this default by specifying the python version as 3.7 when creating the environment you will be working in for this course. You can access conda via the console to make sure it’s properly installed. For instance, you can run conda -V to display the version. On Windows, to access conda via the console please use “Anaconda Prompt” or “Anaconda Powershell Prompt” instead of “Command Prompt”. Environment Environments are used to keep different python versions and packages isolated from each other, generally each project/application will have an independent python environment. For example, we will be using Python 3.7 and packages like numpy, networkx etc, and we want them to be isolated from any other python projects you might have. To create a new environment simply run: conda create –name ai_env python=3.7 -y Once it’s created you can activate it by running: conda activate ai_env The environment is not attached to any specific folder, and you can freely navigate to different directories while it’s activated. If you want to change the environment you can deactivate it using conda deactivate and then activate another env. To see the list of all environments you have on your machine you can run conda env list. PackagesWe will be using multiple python packages throughout this class. Here are some of them: jupyter – interactive notebook (you will learn more about them soon) numpy – a package for scientific computing (multi-dimensional array manipulation) matplotlib – a plotting library networkx – a package for manipulating networks/graphs pandas – a package for data analysis pgmpy – library for probabilistic graphical models You can see the complete list of packages and required versions in ./requirements.txt. We can install all these packages using command pip install -r requirements.txt. Please navigate to the assignment_0/ directory, activate your environment (conda activate ai_env), then run: pip install -r requirements.txt Once installed, you can run pip freeze to see the list of all of the packages installed in your ai_env environment. JupyterNow that you have set up the environment it’s time to learn more about the jupyter notebooks. We have already installed jupyter. To open it up you can run: jupyter notebook It will start a python kernel which you can access via https://localhost:8888 in your browser. For the rest of the assignment proceed to notebook.ipynb. Summary You have now installed conda package and environment manager, created a python environment and installed all the necessary packages. Please always remember to run: conda activate ai_env to activate your environment before you start working on your assignments.
Version: 1.0 Changelog1 Rules • Read the entire document before starting. Critical pieces of information and hints might be provided along the way. • Unfortunately, experience has shown that there is a high chance that errors in the project description will be found and corrected after its release. It is your responsibility to check for updates on Canvas, and download updates if any. • Make sure that all your code is written according to C11 or C++20 standards, using only the standard libraries. 2 Introduction This project is split into two parts; the Branch Predictors and the Out-of-Order Processor. Please refer to Section 3 for information on implementing the Branch Predictors, and refer to Section 4 for information on implementing the Out-of-Order Processor. In this section, we will discuss simulator parameters and trace files, which are shared by both parts of the project. 2.1 Simulator Parameters The following command line parameters can be passed to the simulator. Details on these parameters can be found in the corresponding sections listed in Section 2: • -x: When enabled, only run the Branch Predictors. • -i: The path to the input trace file • -h: Print the usage information. 2.1.1 Branch Predictor Specific Parameters • -b: Select the Branch Predictor to use. – 0: Always Taken (provided) – 1: Two-bits Smith Counter (provided) – 2: Yeh-Patt (for students in ECE 6100 & CS 6290) – 3: GShare (for everyone) • -p: Log2 of the number of entries in the Pattern Table for Yeh-Patt, or the number of 2-bit counters in GShare. – Restriction: P ≥ 9, small pattern tables are not very performant. • -H: Log2 of the number of entries in the History Table for Yeh-Patt. – Restriction: H ≥ 9, small history tables are not very performant. 2.1.2 Out-of-Order Processor Specific Parameters • -a: The number of Addition (ALU) function units in the Execute stage. • -m: The number of Multiply (MUL) function units in the Execute stage. • -l: The number of Load/Store (LSU) function units in the Execute stage. • -s: The number of reservation stations per function unit. The scheduling queue is unified, which means that s × (a + m + l) reservation stations are shared by all function units. • -f: The “Fetch Width”, which is the number of instructions fetched/added to the Dispatch queue per cycle. • -d: This flag has no argument; if it is passed, cache misses and mispredictions are disabled by the driver. Note that the upper bounds for some parameters are not defined. You will need to constraint these in the experiments according to Section 8. 2.2 Trace Format Each line in a trace represents the following: That is, the instructions are effectively already decoded for you. Each register number is in the range [0,31], except when a register is −1, which indicates there is no destination register or that source register is not needed. The Branch Misprediction, I-Cache Miss, and D-Cache Miss flags are set to 1 (or otherwise appropriately) when the corresponding events occur. The opcodes map to the following operations and Function Units: Opcode Operation Function Unit 2 Add ALU unit 3 Multiply, Divide, or Float MUL unit 4 Load LSU unit 5 Store LSU unit 6 Branch ALU unit3 Branch Predictor Specifications Recall from lectures that branch prediction has 3 W’s: Whether to branch, Where to branch (if the branch is taken) and Which instruction is a branch. In this project we will concern ourselves with only the first W (i.e. Whether a branch is taken or not). We have provided you with a framework that reads in branch traces generated from the execution of various benchmarks (see Section 6) and drives your predictors. The simulator framework supports configurable predictor parameters. Your task will be to write functions called by the driver that initialize the predictor, perform a branch direction prediction, update the predictor state, and finally update the statistics for each branch in the trace. 3.1 Basic Branch Predictor Architecture Your simulator should model a GShare predictor (for everyone) and a Yeh-Patt predictor (for students in ECE 6100 & CS 6290). Figures 1 & 2 show the architecture diagrams of the GShare and Yeh-Patt branch predictors, respectively. The driver for the simulation chooses the predictor based on the command line inputs, and calls the appropriate functions for prediction and update. 3.2 The GShare Predictor (everyone) GShare is a cheap branch predictor discussed in class which hashes the PC and GHR to index into a table of Smith counters [1, 2].Figure 1: The architecture of the GShare branch predictor • The Global History Register is a P bits wide shift register. The most recent branch is stored in the least-significant-bit of the GHR. A value of 1 denotes a taken branch and a value of 0 denotes a not taken branch. The initial value of the GHR is 0. – When you update the GHR, shift the GHR left by 1 and set the lowest bit based on the branch outcome. • The Table contains 2P smith counters. The Predictor hashes the GHR with the branch PC to index into the table. • The simulator will use the hash function: Hash(GHR, PC) = GHR L PC[2 + P − 1 : 2], where L is the XOR operator. For example, when PC = 0x000CandP = 2, PC[2 + P − 1 : 2] = PC[3 : 2] = 0b11. • Each Smith Counter in the Table is 2-bits wide and initialized to 0b01, the Weakly-Not-Taken state. 3.3 The Yeh-Patt Predictor (ECE 6100 & CS 6290) A two level adaptive branch predictor [2].Figure 2: The architecture of the Yeh-Patt branch Predictor • The History Table (HT) contains 2H, P-bit wide shift registers. The most recent branch is stored in the least-significant-bit of these history registers (based on the branch pc). A value of 1 denotes a taken branch and a value of 0 denotes a not taken branch. – When you update a history table entry, shift it left by 1 and set the lowest bit based on the branch outcome. • The predictor uses bits [2 + H − 1 : 2] of the branch address (PC) to index into the History Table. All entries of the history table are set to 0 at the start of the simulation. • The Pattern Table (PT) contains 2P smith counters. The value read from the History Table is used to index into the pattern table. • Each Smith Counter in the PT is 2-bits wide and initialized to 0b01, the Weakly-Not-Taken state. • This makes the total predictor size for the Yeh-Patt Predictor 2H∗ P + 2 ∗ 2P bits. 3.4 Simulator Operation The simulator operates in a trace driven manner and follows the below steps: • The appropriate branch predictor initialization function is called, where you setup the predictor data structures, etc. • Branch instructions are read from the trace one at a time and the following operations ensue for each line of the trace: – The driver calls the update prediction stats function. Here the actual behavior of the branch is compared against the prediction. A branch is considered correctly predicted if the direction (TAKEN/NOT-TAKEN) matches the actual behavior of the branch. Stats for tracking the accuracy of the branch predictor are updated here. – The branch predictor is updated with the actual behavior of the branch. • A function to cleanup your predictor data structures (i.e. The destructor for the predictor) and a function to perform stat calculations is called by the driver. Please find more details of the provided framework for the branch predictor in Section 6. 4 Out-of-Order CPU Specifications In this section, you will implement a simulator for a CPU using tagged Tomasulo. Your simulator will take in a handful of parameters that are used to define the processor configuration; see Section 2.1.2 for more information. The provided code will call your per-stage simulator functions in reverse order to emulate pipelined behavior. For details on the provided framework, see Section 6.2. Please read the following subsections carefully for information on simulator functionality. 4.1 Basic Out of Order Architecture Your simulator will implement the stages of a fire out-of-order complete out-of-order (FOCO) processor using Tomasulo’s Algorithm with tags. In order to enable correct behavior with memory operations in parallel, the CPU uses a memory disambiguation algorithm. Figure 3 is a diagram of the general architecture of the model you will simulate. All edges passing through a dotted line will write to their relevant buffers/latches on the clock edge. 4.2 Fetch and The Driver The driver exposes the instruction cache (I-cache) to you via the function procsim driver read inst(). The driver will return 1 instruction per call to procsim driver read inst(). Every cycle, you read -f instructions from the driver and append them to the dispatch queue (if there is room). In the event of a mispredicted/faulting instruction, the driver will first return the instruction, but subsequent calls will return NULL (a NOP) until you set retired mispredict out to true in stage state update(). When you do this, procsim do cycle will update the appropriate statistic. This models the time it takes for the misprediction/fault to be corrected. The instructions from the wrongly predicted path are not provided by the trace, so we fetch NOPs instead. In the event of an I-Cache miss, the driver will handle this for you in terms of emulating correct behavior. The driver will return NOP instructions until it resolves the I-Cache miss, at which point it will resume returning valid instructions. In the event of an I-Cache miss, NOP instructions should be added to the dispatch queue as if they were a normal instruction. You can get the cause of the NOP using the value of driver read status t set by procsim driver read inst. 4.3 Dispatch In Dispatch, we will attempt to fill as many reservation stations in the scheduling queue as possible with instructions from the head of the dispatch queue. You should also set values in the memory alias table for certain instructions (see Section 4.3.1). Remember that instructions are dispatched in program order. The Dispatch stage can continue to dispatch instructions (remove instructions from the dispatch queue) until one of the following condition is met: • If there is nothing in the dispatch queue, you must stall. • If the scheduling queue is full, you must stall. • The Dispatch stage will allocate room in the ROB for the instruction as it places it into a reservation station, so if there is not sufficient room in the ROB, then Dispatch should stall.Figure 3: Overview of the Out of Order Architecture. An arrow that crosses a dotted line indicates that the value is latched at the end of a cycle. An arrow that does not cross a dotted line indicates that the associated action occurs within the clock cycle. • If you already dispatched procsim conf t.dispatch width NOPs in this cycle, you must stall. • If you already dispatched procsim conf t.dispatch width instructions that are not NOPs in this cycle, you must stall. For source registers of an instruction, dispatch will use the tags and ready bits from the messy register file to set up the reservation station in the scheduling queue. For the destination register, dispatch allocates a new tag for it even if the instruction actually doesn’t have destination. If it does have a destination register, you clear the ready bit of the destination register in the messy register file and assign this new tag to that register, otherwise you don’t. Dispatch also allocates a second new tag for the “memory destination register” of each instruction (see Section 4.3.1 for details). When you initialize the dispatch queue, its length should be equal to f×32, where f is fetch width and 32 is the number of registers. 4.3.1 Memory Disambiguation In Tomasulo’s algorithm, register numbers cannot capture data dependence in the memory. This causes program correctness issues. For example, consider the following sequence of memory instructions: 1: SW r5, 0(r6) # (no dest, src1=r5, src2=r6) mem[r6 + 0] = r5 2: LW r7, 0(r8) # (dest=r7, src1=r8, no src2) r7 = mem[r8 + 0] If r6 and r8 hold the same value, there is a read after write data dependency at mem[r6+0]. Because instructions 1 and 2 do not share any registers, the original Tomasulo’s Algorithm cannot capture the potential data dependency for this specific case. You will need to implement the following memory disambiguation algorithm to ensure that we do not violate program correctness. Provided memory traces contain load store addr for all load/store instructions. The memory disambiguation algorithm adds extra “memory source registers (ms)” and “memory destination registers (md)” to load/store instructions. Since both load and store will only operate on one address at a time, ms and md are always the same. The register number is determined by the hash of the load store addr, which is load store addr[11:6]. For example, assume both load/store instructions access memory location 0x01f0 in the following code sequence: 1: SW: (no dest) | src1=r5 , src2=r6 # SW r5, 0(r6), addr=0x01f0 2: ADD: dest=r9 | src1=r10, src2=r11 # ADD r9, r10, r11 3: LW: dest=r7 | src1=r8 , (no src2) # LW r7, 0(r8), addr=0x01f0 The address 0x01f0 hashes to 7. That means we need to add “memory register 7”. Now the code becomes the following: 1: SW: md=m7 , (no dest) | ms=m7 , src1=r5 , src2=r6 # SW r5, 0(r6), addr=0x01f0 2: ADD: (no md), dest=r9 | (no ms), src1=r10, src2=r11 # ADD r9, r10, r11 3: LW: md=m7 , dest=r7 | ms=m7 , src1=r8 , (no src2) # LW r7, 0(r8), addr=0x01f0 To implement this memory disambiguation algorithm, we need a “memory alias table” that stores 64 “memory registers”. The data structure should be same as the normal register file, where each entry contains a tag and a ready bit. We also need extra fields in each entry of the scheduling queue: md tag, ms tag, and ms ready. The result buses should also update corresponding entries in the register file and the scheduling queue. By hashing the load/store addresses to ”memory registers”, we can treat these registers as if they were real registers and run Tomasulo’s algorithm. For example, when scheduling load/store instruction, you do something like (lets say rs is a scheduling queue entry and MAT is the memory alias table): rs.ms_tag = MAT[inst.ms].tag rs.ms_ready = MAT[inst.ms].ready rs.md_tag = unique_tag() Note that is just part of the code and you still need to handle the regular registers. Also notice that even though a load instructions just reads memory, we consider it to have a md and assign a new tag to it. This way when a load instruction is followed by a store instruction that writes the same address, the store instruction will have a dependency on the load instruction, thus preserving the load/store order. In order to ensure determinism and match the solution, if multiple instructions can be fired at the same time, they are fired in program order (but still within the same cycle if possible). This means that if 2 instructions are both ready for a single function unit, the instruction that comes first in program order would fire first. Use inst t.dyn instruction count as a mechanism to determine program order. It will also be helpful to ensure that dispatch only adds instructions to the “end” of the scheduling queue. 4.5 Execute In the execute stage you will move every instruction through its associated function unit and onto a result bus when it completes. Then you will use the result buses to update processor state. 4.5.1 ALU This is a single-stage unit. 4.5.2 MUL 4.6 LSU This is a single-stage unit. We assume the Load/Store units are not pipelined. The traces have been annotated with I-Cache misses and D-Cache misses. In a real processor, the Load/Store units would access the data cache (dcache) in-order to access or manipulate data. However, our traces are pre-labeled with I-Cache and D-Cache misses (see Section 2.2), meaning that the cache accesses have already been emulated for you. You will need to stall the LSU units depending on the trace labels and the instruction type. Because we do not model a store buffer or load/store queue, stores will never stall, and instead only take a single cycle. However, loads will take a variable number of cycles, depending on the cache access result inst t.dcache hit: • CACHE LATENCY L1 HIT: 2 cycles (L1 HIT CYCLES) • CACHE LATENCY L2 HIT: 10 cycles (L2 HIT CYCLES) • CACHE LATENCY L2 MISS: 100 cycles (L2 MISS CYCLES) Noted that L2 HIT CYCLES is the total number of cycles that includes the time to miss in L1 and hit in L2. Similarly, L2 MISS CYCLES includes the time to miss in L1 and L2 and get data from the memory. You don’t need to change the stats of I-Cache misses and D-Cache misses because the driver tracks it for you. These values are defined in procsim.hpp. 4.6.1 Result Buses Completed instructions are removed from the scheduling queue. These busses will also place the instruction in the ROB in program (tag) order. All of this happens within the same cycle! Note that there are A + M + L result busses, thus instructions never stall waiting for a free result bus. 4.7 State Update State Update is where we will update the architectural state of the processor. Every cycle, you will, in program order, retire a number of instructions up to ”retire width” from the ROB. The retire width is equal to the fetch width (defined by -f). In a real processor, you would also commit their destination register values (if present) to the Architectural Register File. However, since we aren’t modeling data in our pipeline, you don’t actually need to do this! You will need to call the provided procsim driver update predictor function to update your branch predictor when you retire a branch instruction. Also, if you retire an instruction with the inst t.mispredict field set to true, set retired mispredict out to true and stop retiring any more instructions. When you create the ROB, make sure its size (num rob entries) is equal to the fetch width (-f) times the number of registers (which is 32 in our scenario). 4.8 Initial Conditions The simulated pipeline should initialize to the following conditions: • Registers in the register file all marked as ready with incrementing tags. R0 has tag 0; R1 has tag 1, …, R31 has tag 31. • MAT also initialized to ready with incrementing tags. M0 has tag 32; M1 has tag 33, …, and M63 has tag 95. • All function units are empty/ready. • All queues and the ROB are empty. 4.9 Queue sizes summary • Size of the dispatch queue is equal to the size of ROB. • Size of the scheduling queue is given by s× (a + m + l) where s, a, m, l are parameters. • Size of the ROB is given by f× 32, where f is fetch width and 32 is the number of registers. 5 Statistics You will need to keep track of the following statistics. They are split up into statistics for the Branch Predictors and Out-of-Order Processor. 5.1 Branch Predictor Statistics More details into these statistics can be found in branchsim stats t struct in branchsim.hpp: • total instructions: Total number of instructions. We will trace this for you in the driver. • numbranch instructions: Total number of branch instructions. • num branches correctly predicted: Total number of branches that were predicted correctly. • num branches mispredicted: Total number of branches that were mispredicted. • prediction accuracy: The accuracy of the Branch Predictor. 5.2 Out-of-Order Processor Statistics More details into these statistics can be found in procsim stats t struct in procsim.hpp: • cycles: The number of cycles that have passed since the processor was started (the provided code increments this statistic for you). • instructions fetched: The number of instructions fetched by the Fetch stage, regardless of whether or not they retire. Do not count NOPs. • instructions retired: The number of instructions that exit the ROB. • no fire cycles: Cycles where nothing in the scheduling queue could be fired. • rob no dispatch cycles: Cycles in which Dispatch stops putting instructions into the scheduling queue only because of the constraint on the maximum number of ROB entries. • dispq max usage: The maximum number of instructions in the dispatch queue during execution. You should update this at the end of procsim do cycle(). • schedq max usage: The maximum number of instructions in the scheduling queue during execution. You should update this at the end of procsim do cycle(). • rob max usage: The maximum number of instructions in the ROB during execution. You should update this at the end of procsim do cycle(). • dispq avg size: The average number of instructions in the dispatch queue during execution. You should update this at the end of procsim do cycle(). • schedq avg size: The average number of instructions in the scheduling queue during execution. You should update this at the end of procsim do cycle(). • rob avg size: The average number of instructions in the ROB during execution. You should update this at the end of procsim do cycle(). • ipc: The average number of instruction retired per cycle. • i cache misses: You do not need to modify this. The number I-Cache misses. The simulator driver tracks this for you. • d cache misses: You do not need to modify this. The number D-Cache misses. The simulator driver tracks this for you. • num branch instructions: You do not need to modify this. The number of branch instructions. The simulator driver tracks this for you. • branch mispredictions: You do not need to modify this, but you need to set (*retired mispredict out) correctly within the stage state update function to get this number correct. The number of branch mispredictions the processor encounters. The provided procsim do cycle() function tracks this parameter for you. • instructions in trace: You do not need to modify this. The number of instructions in the trace. The simulator driver tracks this for you. 6 Implementation Details You have been provided with the following files: • branchsim.cpp – Your Branch Predictor implementations will go here. • branchsim.hpp – You do not need to modify this file. Header file containing useful definitions and function declarations for the branch predictors. • Counter.cpp – You do not need to modify this file. Implementation of the Counter struct functions. • Counter.hpp – You do not need to modify this file. Header file containing Counter struct and function definitions. • procsim.cpp – Your processor implementation will go here. • procsim.hpp – You do not need to modify this file. Header file containing definitions shared between your simulator and the driver. • proj2 driver.hpp – You do not need to modify this file. Provided code that reads a trace, maintains a pointer to the next instruction in the trace, and allows your simulator code to read it via procsim driver read inst(). The simulator invokes your procsim do cycle() function repeatedly until all trace instructions have been retired. • run.sh: A shell script that invokes your simulator. You only need to change this if you have made the highly discouraged choice to write your simulator without the provided framework. • validate grad.sh (for students in ECE 6100 & CS 6290): You do not need to modify this file. A shell script which runs your simulator and compares its outputs with the reference outputs. • validate undergrad.sh (for students in ECE 4100 & CS 4290): You do not need to modify this file. A shell script which runs your simulator and compares its outputs with the reference outputs. • Makefile: A Makefile that contains the logic needed to compile your code. It has some useful features: – make validategrad will compile your code and run validate grad.sh. – make validate undergrad will compile your code and run validate undergrad.sh. – make submit will generate a submission tarball for Gradescope. – make clean will clean out all compiled files. – make FAST=1 will compile with -O2 (You should run make clean first). – make SANITIZE=1 will compile your code for use with Address-Sanitizer. (You should run make clean first). If your simulator is seg-faulting but valgrind cannot find the error, address sanitizer is a stricter framework that is capable of finding memory bugs in global/stack space and the heap. • traces/: A directory containing execution traces from real programs run on a RISC-V simulator; their format is detailed above in Section 2.2. The driver will read these for you: – mcf505: A trace from a program for vehicle scheduling in mass public transportation. It consist mostly of integer arithmetic. – deepsjeng531: A trace for a program based on the 2008 Computer Speed-Chess Champion. It estimates the best move using multiple heuristics; including alpha-beta tree search, forward pruning, and move ordering. – leela541: A trace for a program for a Go playing engine. It uses Monte Carlo position estimation and selective tree search. – xz557: A trace from a program based on XZ Utils 5.0.5; a data compression and decompression utility. – nab544: A trace from a program based on Nucleic Acid Builder (NAB), which is a molecular modeling application that performs the types of floating point intensive calculations that occur commonly in life science computation. The calculations range from relatively unstructured ”molecular dynamics” to relatively structured linear algebra. 6.1 Provided Framework for Branch Predictor We have provided you with a comprehensive framework where you will add data structure declarations and write the following functions for each branch predictor (We have also provided implementations for 2 predictors for you for your reference): • void _init_predictor(branchsim_conf *sim_conf) Initialize class variables, allocate memory, etc for the predictor in this function • bool _predict(branch *branch) Predict a branch instruction and return a bool for the predicted direction {true (TAKEN) or false (NOT-TAKEN)}. The parameter branch is a structure defined as: typedef struct branch_t { uint64_t ip; // Branch address (PC) uint64_t inst_num; // Instruction count of the branch bool is_taken; } branch; // Actual branch outcome • void _update_predictor(branch *branch) Function to update the predictor internals such as the history register and Smith counters, etc. based on the actual behavior of the branch • void _cleanup_predictor() Destructor for the branch predictor. De-allocate any heap allocated memory or other data structures here. Apart from the per predictor functions, you will need to implement some general functions for book-keeping and final statistics calculations: • void branchsim_update_stats(bool prediction, branch_t *br, branchsim_stats_t *sim_stats); Function to update statistics based on the correctness of the prediction (you can use the is taken field of the branch to check if the branch was actually taken or not). • void branchsim_finish_stats(branchsim_stats_t *sim_stats); Function to perform final calculations such as misprediction rate, etc 6.2 Provided Framework for OOO Processor For the Out-of-Order processor, we have provided multiple empty functions representing different pipeline stages. Please refer to Section 4 for information on pipeline stage functionality. There are also empty function definitions for initializing your pipeline variables and calculating statistics. All of these functions can be found in procsim.cpp, with detailed comments explaining what each function should do. Fill in any function that has a TODO comment. However, we do provide the implementation for procsim do cycle(), which invokes the pipeline stage functions in reverse order to prevent you from needing to manage pipeline buffers by hand. You will need to keep track of certain statistics for your pipeline. The provided header file procsim.hpp contains the procsim stats t struct, which you will need to fill with the proper values. Please see Section 5 for details of what each statistic should track/represent. 6.3 Docker Image We have provided an Ubuntu 22.04 LTS Docker image for verifying that your code compiles and runs in the environment we expect — it is also useful if you do not have a Linux machine handy. To use it, install Docker (https://docs.docker.com/get-docker/), extract the provided project tarball, and run the 6290docker* script in the project tarball corresponding to your OS. You do not need to use the graphical application that comes with Docker. Running the previous script should open an 22.04 bash shell where the project folder is mounted as a volume at the current directory in the container, allowing you to run whatever commands you want, such as make, gdb, valgrind, ./proj2sim, etc. Note: Using this Docker image is not required. If you have a Ubuntu 22.04 system or environment available, you can verify that your code compiles on that system. We will also set up a Gradescope autograder that automatically verifies if we can successfully compile your submission, so if your submission passes the Gradescope compilation step, then there is no need to verify with Docker or an Ubuntu 22.04 system. 7 Validation Requirements You must run your simulator and debug it until the statistics from your solution perfectly (100 percent) match the statistics in the reference outputs for all test configurations. This requirement must be completed before you can proceed to Section 8 (Experiments). You can run make validate undergrad or make validate grad to compare your output with the reference outputs. 7.1 Debug Outputs We have provided debug outputs for you in the debug outs directory. Note that we only used the shorter traces (50K), not the full length traces (2M). We produced these debug traces by running med nomiss, med always taken, med, big, and tiny for all 5 benchmarks. These are the flags for each of the above configurations: • med nomiss (branch mispredictions and cache misses disabled): -b 3 -p 15 -s 5 -a 3 -m 2 -l 2 -f 4 -d • med always taken (branch predictor always predicts taken): -b 0 -s 5 -a 3 -m 2 -l 2 -f 4 • med: -b 3 -p 15 -s 5 -a 3 -m 2 -l 2 -f 4 • big: -b 3 -p 15 -s 8 -a 4 -m 3 -l 2 -f 8 • tiny: -b 3 -p 15 -s 4 -a 1 -m 1 -l 1 -f 2 We have also provided branchsim cpp debug printfs.txt and procsim cpp debug printfs.txt, which contains all of the print statements in the simulator used to generate the debug outputs. The print statements already written in the provided template code is not included. To enable debug output generation in your own code, use make DEBUG=1 (you should make clean first!) which will allow you to use preprocessor directives to control whether or not your code generates print statements, like this: #ifdef DEBUG printf(“Yeh-Patt: Creating a history table of %” PRIu64 ” entries of length %” PRIu64 ” “, myvar1, myvar2); #endif Please do not submit code that always generates debug outputs (that is, it prints without the #ifdef DEBUG … #endif directives), as this will break the autograder and cause you to not match reference outputs. 7.2 Debugging 8 Experiments Once your simulator has been validated and matches the ref outs, you will need to find the optimum pipeline configuration for each trace (Only consider the full length traces: traces/* 2M.trace). This means you will submit 5 configurations. An optimal pipeline has the best possible IPC (Instructions Per Cycle) with the lowest resource utilization. Here are the constraints for your experiments. See Section 2.1 for a detailed explanation of the meaning of these parameters: • Don’t pass -x or -d. • If -b is 2 (Yeh-Patt): – -p: 14-15. – -h: 11 when -p is 14, 12 when -p is 15. • If -b is 3 (Gshare): – -p: 15-16. • -s: 4-8. • -a: 1-4. • -m: 1-3. Cannot be larger than -a. Additionally, must be at least 2 if -a is 3 or greater. • -l: 1-2. Must be 2 if -a is greater than 2. • -f: 2, 4, or 8. Must be greater than or equal to the maximum value of -a, -m, and -l. While we do not require you to search the entire space of configurations, you will need to search a large portion of it to ensure you are not missing information that is crucial to your decision making process. Within these constraints, you are expected to find a configuration that performs at least 90% as well as the best performer and uses as few resources as possible. You should consider the impact of each architectural knob on the architecture as a whole. When evaluating whether a configuration is optimal, consider the statistics you are calculating beyond just IPC. You are responsible for defining “resources” however you see fit. So long as your justification and reasoning are sound, many interpretations will be accepted. Your report must contain a justification for why your chosen configuration is ideal. Include evidence and analysis in terms of plots, explanations, research, and logic. Ensure that the report is in a file named report.pdf. Please submit a PDF file: do not submit any other file types (ex. Microsoft Word). 9 What to Submit to Gradescope Please run make submit and submit the resulting tarball (tar.gz) to Gradescope. Do not submit the assignment PDF, traces, or other unnecessary files (using make submit avoids this). Running make submit will include PDFs in the project directory in the tarball, but please make sure that the command ran successfully and your experiments report PDF is present in your submission tarball. We will create a simple Gradescope autograder that will verify that your code compiles and matches the 10 million–branch gcc trace and a subset of the other reference traces. This autograder is a smoke test to check for any incompatibilities or big issues; it is not comprehensive. Make sure you untar and check your submission tarball to ensure that all the required files are present in the tar before making your final submission to Gradescope! 10 Grading You will be evaluated on the following criteria: +50 : You turn in well commented significant code that compiles and runs but does not match the validation. +10 : Your simulator completely matches the validation outputs for the branch predictors. +25 : Your simulator completely matches the all validation outputs. +10 : You ran experiments and found the optimum configuration matching the constraints in the Experiments section and presented sufficient evidence and reasoning. Points for the experiments and/or the memory leak check cannot be awarded without first matching all validation traces. This is non-negotiable.• Copy/share code from/with your fellow classmates or from people who might have taken this course in prior semesters. • Publish your assignments on public repositories, github, etc, that are accessible to other students. • Submit an assignment with code or text from an AI assistant (e.g., ChatGPT). • Look up solutions online. Trust us, we will know if you copy from online sources. Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct. Appendix B – Helpful ToolsYou might the following tools helpful: • gdb: The GNU debugger will prove invaluable when you eventually run into that segfault. The Makefile provided to you enables the debug flag which generates the required symbol table for gdb by default. – You can invoke gdb for the with gdb ./proj2sim and then run run -i traces/ at the gdb prompt. • Valgrind: Valgrind is really useful for detecting memory leaks. Use the following command to track all leaks and errors for the simulator: valgrind –leak-check=full –show-leak-kinds=all –track-origins=yes ./proj2sim -i traces/ References [1] S. McFarling, “Combining Branch Predictors,” 1993. [2] T.-Y. Yeh and Y. N. Patt, “Two-level adaptive training branch prediction,” in Proceedings of the 24th Annual International Symposium on Microarchitecture, ser. MICRO 24. New York, NY, USA: Association for Computing Machinery, 1991, p. 51–61. [Online]. Available: https://doi.org/10.1145/123465.123475
SL1 ≥ 0. All files from the new tar ball ex cept for cachesim.cpp have changed. Clar ified • grad sec tion re quire ments. 2 Rules • This is a tough assignment that requires a good understanding of concepts before you can start writing code. Make sure to start early. • Read the entire document before starting. Critical pieces of information and hints might be provided along the way. • Unfortunately, experience has shown that there is a high chance that errors in the project description will be found and corrected after its release. It is your responsibility to check for updates on Canvas, and download updates if any. • Make sure that all your code is written according to C11 or C++20 standards, using only the standard libraries. 3 Background 3.1 Prefetcher (+1 and Strided) In this project we will use two prefetching schemes. The first one being a simple +1 Prefetcher and the second one being a Strided Prefetcher. Since the minimum unit the Prefetcher can fetch is a block, we only use the block address and ignore the block offset. Where “block address” is the concatenation of the tag and the index. +1 Prefetcher: On a miss on block at block address X, if the next block (block at block address (X + 1)) is not in the cache, prefetch that block and insert it into the L2 cache. Prefetch (X + 1) only after inserting block X into the cache. Strided Prefetcher: On a miss on a block at block address X, then on a block at block address Y , prefetch the block at block address Y +k where k = Y −X, if block at address Y + k is not in the cache. k is the difference between the current miss and the previous. Prefetch (Y + k) only after the block at block Y is inserted into the cache. 3.1.1 Insertion Policies (MIP and LIP) In this project, we will consider two cache insertion policies when dealing with prefetching. The first is the standard insertion policy used in LRU replacement, which we call “MIP” for clarity: MRU Insertion Policy (MIP): The MRU insertion policy means that new blocks are inserted in the MRU position. MRU insertion policy is originally defined only under the LRU replacement policy. For this project, we extend the definition of MIP under the LFU replacement policy. In this project, we define the MIP under LFU as setting the MRU bit of a block and clear other the MRU bit of every other block in the same set. LRU Insertion Policy (LIP): Designed for L2 caches to avoid thrashing on workloads with low temporal locality, LIP inserts all new blocks at the LRU position. Similarly, for this project, we define of LIP under the LFU replacement policy. We define LIP under LFU as clearing the MRU bit of the inserted block and leaving the MRU bit of other blocks in the set unmodified. 4 Simulator Specifications In this project, you will build a simulator with a write-back, write-allocate L1 cache, and a write through, write-no-allocate L2 cache. Your simulator will receive a series of memory accesses from the CPU in a provided trace and must print some final statistics before exiting. 4.1 Simulator Configuration Both the L1 and L2 caches should implement LRU replacement (for everyone) and LFU replacement (for students in 6100 & 6290). The L1 cache follows the write-back, writeallocate write strategy. The L2 cache shares the L1 block size (B parameter) and follows the write-through, write-no-allocate write strategy. The system uses 64-bit addresses. The L1 cache in your simulator will have the following configuration knobs: • -c < CL1 >: A total size of 2CL1 bytes • -b < B >: Block size of 2B bytes. This will also be the block size used for the L2 cache Restriction: The block size must be reasonable: 5 ≤ B ≤ 7 • -s < SL1 >: 2SL1-way associativity Restriction: SL1 ≥ 1 0 The L2 cache in your simulator will have the following configuration knobs: • -D: if this flag is supplied, the L2 cache is Disabled, it is enabled otherwise • -C < CL2 >: A total size of 2CL2 bytes Restriction: The size of the L2 cache must be strictly greater than the size of the L1 cache (CL2 > CL1) • -S < SL2 >: 2SL2-way associativity Restriction: The associativity of the L2 cache must be greater than the associativity of the L1 cache (SL2 > SL1) Restriction: The L2 CL2 − SL2 must be greater than the L1 CL1 − SL1 • -P < 0,1,2 >: Sets the type of prefetcher to use – 0: Disable prefetcher – 1: Use +1 prefetcher Everyone – 2: Use Strided Prefetcher students in 6100 & 6290 • -I : Prefetcher Insertion Policy The following parameters apply to the entire simulation: • -r : Replacement policy for both caches: LRU (Everyone) or LFU (LFU is for students in 6100 & 6290) • -f : The filename/path for the trace to execute 4.2 Simulator Semantics 4.2.1 L1 And L2 Obliviousness In this project, the L1 cache does not know about the L2 cache, and vice versa. The bus connecting L1 to L2 is the width of an L1 cache block. Effectively, the L1 cache believes it is talking to memory, and the L2 cache believes it is talking to the CPU. For example, the L2 cache sees a write-back from L1 as a write to L2. So even during writebacks from L1, your L2 cache simulation code should increment L2 hit/miss statistics counters. Also, when performing a write to L2, if the block is present in L2 already, that block should be moved to the MRU position. (If the written block is not present in L2, do not add it, because L2 is write-through and write-no-allocate.) The L2 cache is write-through, meaning that the values in the L2 cache are always in sync with values in memory. Note that a write miss in L1 will first read the block from L2 and then update the L1 copy with the write. 4.2.2 Prefetching Prefetching in the cache system is a trick that uses spatial/sequential locality to try to predict what blocks might be needed in the future. The main two types of prefetching schemes that we are going to implement in this cache system are the +1 prefetch and the strided prefetch. +1 Prefetching On an L2 cache read miss, we fetch the missing block from memory, but also fetch the next block in memory and bring it into the cache. If the next block is already in cache, we skip the prefetch. Strided Prefetching (for students in 6100 & 6290) 4.2.3 LRU Replacement and Tracking One possible way to implement the LRU Replacement Policy is to use timestamp counters. We strongly recommend using timestamps to implement LRU tracking for this project as it follows the same logic of our implementation. To use this implementation, you need to keep track of the counter value where a certain block has been used and update it every time that block is used. This needs to be done per cache as there is possible cases where the LRU is different in the L1 cache and in the L2 cache. When it comes to evict a block, simply look through the timestamps associated with each block and evict the one with the farthest back (smallest) timestamp. Here is how you will use and manage the timestamp counter. • First, you initialize the cache’s timestamp counter to the value 2(C−B+1). • In cases where the block of current access or the block you want to prefetch is already in the cache: – If the block of current access is already in cache, you set the timestamp of the block to the current value of the timestamp counter. This acts like setting the block to most recently used. After access, you increment the timestamp counter by 1. – For MIP, you set the timestamp of the newly installed block to the current value of the timestamp counter. After insertion, you increment the timestamp counter by 1. – For LIP, you set the timestamp of the newly installed block to lowest − 1. After insertion, you increment the timestamp counter by 1. We define lowest as the smallest timestamp of all valid blocks in the set you want to install a new block into. If there is no valid block in the set before insertion, lowest is undefined. In this case where lowest is undefined, you set the timestamp of the newly installed block to current value of the timestamp counter. 4.2.4 LFU Replacement and Tracking Note: Implementation of LFU Replacement Policy is for students in 6100 & 6290. To implement the LFU Replacement Policy, you must keep a counter of how many times a certain block is used and refer to the counter when deciding which block to evict. However, the naive LFU Replacement Policy has one huge fatal flaw. Imagine missing on a block with a full cache. When you bring in that new block, you replace the LFU, but now that new block is most likely the LFU. If the next access is also a miss, then that next block will replace the block that you just brought in. This is very inefficient and goes against temporal locality, therefore we will use the MRU bit to prevent this case. The MRU bit serves as a way to prevent a block from being evicted. When it comes to evict a block, simply check each counter for each block and evict the one with the lowest counter with the restriction that you do not evict the block that has the MRU bit set. In the cases where multiple blocks are equal in terms of frequency of use, break the tie by choosing to evict the block with the smallest tag. We track LFU status by having a “use” counter for each block that counts how many times it has been used and a MRU bit for each block that tells us if it is the MRU block in the set. • In cases where the block of current access or the block you want to prefetch is already in the cache: – If the block of current access is already in cache, you set the MRU bit of the block and clear the MRU bit of every other block in the same set. After access, you increment the block’s “use” counter by 1. – For MIP, you set the MRU bit of this new block and clear the MRU bit of every other block in the same set. – For LIP, you clear the MRU bit of this new block. You leave the MRU bit of the other blocks in the set unmodified. • If the newly installed block is the block of current access, set the “use” counter to 1. If the newly installed block is the block you prefetched, set the “use” counter to 0. 4.2.5 Serial Checks 1. Check L1 cache 2. Check L2 cache However, your simulator should increment hit/miss counters for the L2 cache only when L1 has missed. Similarly, blocks in L2 should not move into the MRU position for an access unless the L1 cache missed. 4.2.6 Do Not Writeback Before L2 Read When the L1 cache misses, please have the L1 cache perform a read from L2 before you write back a dirty victim block to L2. Otherwise, if the block written back and the requested block share an L2 set, their positions in the LRU queue for their L2 set could be swapped compared to the expected behavior. 4.2.7 Disabling Caches For simplicity, when the L2 cache is disabled, it should act as an zero-sized write-through cache: it should miss on every read, and send all writes directly to DRAM. L2 statistics still need to be updated and printed in this case. However, if the L2 cache is disabled, please set its hit time (HT) to zero. 4.3 Simulator Statistics Your simulator will calculate and output the following statistics: • Overall statistics: – Reads (reads): Total number of cache reads – Writes (writes): Total number of cache writes • L1 statistics: – L1 accesses (accesses l1): Number of times L1 cache was accessed – L1 hits (hits l1): Total number of L1 hits. – L1 misses (misses l1): Total number of L1 misses. – L1 hit ratio (hit ratio l1): Hit ratio for L1, calculated using the first three L1 stats above. – L1 miss ratio (miss ratio l1): Miss ratio for L1, calculated using the first three L1 stats above. – L1 AAT (avg access time l1): See Section 4.3.1 • L2 statistics: – L2 reads (reads l2): Number of times the L2 cache received a read request. This stat should not be touched unless there was L1 read miss – L2 writes (writes l2): Number of times the L2 cache received a write request. This stat should not be touched unless there was a write-back from L1 cache – L2 read hits (read hits l2): Total number of L2 read hits. This stat should not be touched unless there was an L1 cache miss – L2 read misses (read misses l2): Total number of L2 read misses. This stat should not be touched unless there was an L1 cache miss – L2 prefetches (prefetches l2): Total number of L2 prefetches. This stat should not be touched unless the block you want to prefetch is not in the cache at the time you want to bring it in. – L2 read hit ratio (read hit ratio l2): Read hit ratio for L2, calculated using earlier L2 read stats. – L2 read miss ratio (read miss ratio l2): Read miss ratio for L2, calculated using earlier L2 read stats. – L2 AAT (avg access time l2): See Section 4.3.1 4.3.1 Average Access Time For the purposes of average access time (AAT) calculation, we assume that: • For L1, hit time is k0 + (k1 × (CL1 − BL1 − SL1)) + k2 × (max(3,SL1) − 3) – k0 = 1ns – k1 = 0.15ns – k2 = 0.15ns • For L2, hit time is k3 + (k4 × (CL2 − BL2 − SL2)) + k5 × (max(3,SL2) − 3) – k3 = 4ns – k4 = 0.3ns – k5 = 0.3ns • The time to access DRAM is 100ns The provided header file, cachesim.hpp, includes constants for these values. These values are in nanoseconds. Please also provide your answer in nanoseconds. AATL1 = HTL1 + MRL1 × MPL1 where the hit time HTL1 is as calculated above, and MRL1 is the L1 miss ratio (miss ratio l1). When computing the AAT for the L2 cache, which is write-through and write-no-allocate, use the L2 read miss ratio (read miss ratio l2) as the miss ratio in the AAT equation. 5 Implementation Details We included a driver, cachesim driver.cpp, which parses arguments, reads a trace from standard input, and invokes your sim access() function in cachesim.cpp for each memory access in the trace. The driver takes a flag for each of the knobs described in Section 4.1; run ./cachesim -h to see the list of options. The provided cachesim.cpp template file also contains sim setup() and sim finish() functions you should complete for simulator setup and cleanup (including final stats calculations), respectively. By default, the provided ./run.sh script invokes the ./cachesim binary produced by linking cachesim driver.cpp with cachesim.cpp. 5.1 Docker Image We have provided an Ubuntu 22.04 LTS Docker image for verifying that your code compiles and runs in the environment we expect — it is also useful if you do not have a Linux machine handy. To use it, install Docker (https://docs.docker.com/get-docker/) and extract the provided project tarball and run the 6290docker* script in the project tarball corresponding to your OS. That should open an 22.04 bash shell where the project folder is mounted as a volume at the current directory in the container, allowing you to run whatever commands you want, such as make, gdb, valgrind, ./cachesim, etc. Note: Using this Docker image is not required if you have a Linux system available and just want to make sure your code compiles on 22.04. We will set up a Gradescope autograder that automatically verifies we can successfully compile your submission. 6 Validation Requirements We have provided six memory traces in the traces/ directory of the provided project tarball. Validation outputs for the default simulator configuration for each of these traces are provided in the ref outs/ directory. There are also validation outputs for gcc under the default configuration except with only L1 (-D), L1 and L2 with prefetcher disabled (-P 0). Given these configurations, the output of your code must match these reference outputs byte-for-byte! We have included a script to compare the output of your simulator to these reference outputs using make validate undergrad (for students in 4100 & 4290) and make validate grad (for students in 6100 & 6290). 6.1 Debug Traces Debugging this project can be difficult, particularly when looking only at final statistics. We have provided some verbose debug traces for you that correspond to the reference traces. To motivate you to use them, part of your grade will depend on you implementing matching debug traces in your own code (see Section 9). Please see the debug outs/README.txt for more information. Note that your debugging statements should only print when a special DEBUG flag is set. Otherwise, it will slow down your implementation and potentially cause issues during grading. To make the debugging statements conditional, use the following code: #ifdef DEBUG // Your debug statement here #endif To see your debugging statements print when you test your implementation, add DEBUG=1 to the make command. 7 Experiments Once you have your simulator working, you should find an optimal cache configuration for each of the six traces that meets the following constraints: 1. Configuration should respect all the restrictions mentioned in Section 4.1 2. The L2 data store is 128KiB (C = 17) 3. The L1 data store is 32KiB (C = 15) An optimal cache configuration would have the lowest average access time, while minimizing metadata/tag storage. Identify points of diminishing returns in terms of cache parameters (C, B, S). Consider that highly associative caches can use substantially more area and power. Include any rationale, quantitatively or qualitatively, to justify your decisions. In your report you must provide, in addition to the cache configuration, the total size of any associated metadata required to build the cache for your recommended configuration(s), except for the LRU/LFU tracking metadata. You should submit a report in PDF format (inside your submission tarball) in which you describe your methodology, rationale, and results. 8 What to Submit to Gradescope Please submit your project to Gradescope as a tarball containing the your experiments writeup as a PDF, as well as everything needed to build your project: the Makefile, the run.sh script, and all code files (including provided code). You can use the make submit target in the provided Makefile to generate your tarball for you. Please extract your submission tarball and check it before submitting! We plan to enable a Gradescope autograder that will verify that your code compiles on 22.04 at submission time and test your implementation. 9 Grading You will be evaluated on the following criterion: +50: You turn in well commented significant code that compiles and runs but does not match the validation +35: Your simulator completely matches the validation output +10: You ran experiments and found the optimum configuration for the ‘experiments’ workload and presented sufficient evidence and reasoning +5: You implement debug outputs as explained in Section 6.1. Your code is well formatted, commented and does not have any memory leaks! Check out the section on helpful tools• Copy/share code from/with your fellow classmates or from people who might have taken this course in prior semesters. • Publish your assignments on public repositories, github, etc, that are accessible to other students. • Submit an assignment with code or text from an AI assistant (e.g., ChatGPT). Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct. Appendix B – Helpful ToolsYou might the following tools helpful: • gdb: The GNU debugger will prove invaluable when you eventually run into that segfault. The Makefile provided to you enables the debug flag which generates the required symbol table for gdb by default. – To pass a trace on standard in (as cachesim expects) while running in gdb, you can invoke gdb with gdb ./cachesim and then run run at the gdb prompt • Valgrind: Valgrind is really useful for detecting memory leaks. Use the following command to track all leaks and errors: valgrind –leak-check=full –show-leak-kinds=all –track-origins=yes ./cachesim
CS 6238: Secure Computer Systems Understanding Memory ProtectionLearning Objectives: The goal of this project is to help students become familiar with memory protection facilities provided by operating systems. In particular, you will learn how to limit access to a certain region of memory (e.g., only read, write or execute access). The project has two parts. First, you will learn about mprotect(), a memory protection system call. In the second part, you will explore why it is a good idea to disable execution on the stack to safeguard a program’s execution. Memory protection is not limited only to these two examples, there are many different methods to protect the stack and heap. You are encouraged to look at and familiarize yourself with other relevant memory protection mechanisms as well. However, to keep this project simple and of limited scope, we will focus only on the protection of the memory by the above two discussed mechanisms. Thus, the objectives of the project are as follows: 1. Understand how mprotect() works and how it can be implemented. 2. Understand the benefits of turning off the executable stack. Project Setup: Note: The link to the VM will be posted on a Piazza pinned post. For this project, you will be provided an Ubuntu-based Virtual Machine (VM). This VM was tested on Oracle VM Virtual box 5.2.16 and can be directly imported to it . This VM has a default account “project1” setup with normal user access privileges. You do not need root account credential for completion of this project. Password for the “project1” account is “CS6238”. You should not include “” while entering the password. When you log into account “project1”, you will find Project_1 folder on Desktop. This folder contains 2 additional folders named, Stack_Protection and M_protect. We are going to use the contents of folder M_protect for completion of Task 1, and similarly contents of Folder Stack_Protection for Task 2. Background: This project assumes that you know the basics of C programming language (or can learn it quickly). More specifically, you should be able to understand and modify a given C code snippet. Second, you should know how a basic buffer overflow works. For the understanding of basic buffer overflow, you can refer to course materials in CS 6035, Intro to Information Security. If not, try some Google-fu.Project Details: For both tasks, you should first do some exploration and then conduct specified experiments or answer some questions based on the learning. The project should be straightforward and is more focused on exploring things and how they work.Task 1: Protection of Memory via mprotect() (50% of grade): This task is divided into two parts, (A) Understanding mprotect(), and (B) Experimenting with programs that use this call. The understanding part is 40% of this task (i.e., 20% of the total grade of this project). The remaining 60% will be for the implementation and experimentation part of this task. Part A) Understanding Memory Protection (20% of grade): To answer: 1. Why do you get SIGSEGV when you execute the object code generated by compiling the mprotect.c program? 2. How does mprotect() protect memory ? What is the minimum size requirement for this call, what happens if you pass the value of the “len” argument as 1? 3. Sam is a programmer and he needs to protect a 0x380 byte block starting at memory address 0x1234000 and ending at address 0x1234379. This block should be protected from overwriting by some other internal function. Can Sam use the mprotect() function in his C program to protect this memory space? Explain your answer. 4. Review and report what data is being protected in mprotect.c by the mprotect() function. Moreover, discuss if any function can perform read or write on the protected data. If the mprotect call is used in multiple instances, write your observations for each of them. Part B) Experimentation and Implementation (30% of grade): 1. Write first n bytes of last two pages (9th and 10th page) with your first name where n is equal to number of characters in your first name. 2. Now, use mprotect() to allow read and write access on 7th and 8th page. Write your last name in first n bytes of 7th and 8th pages, where n is equal to number of characters in your last name and then try to read it. You should display it on output screen (print to STDOUT). 4. Now, create a buffer of 2 pages and try to copy 7th and 8th page into it. Can you copy it, if not why? 5. Now try to copy 6th page and 9th page into the previously created buffer. Are you able to do so? If not, when your code hit SIGSEGV, is it copying 6th or 9th page? Explain your answer. All the above steps should be followed in the same order, and updates should be made to the same script. Deliverables for Task 1: 1. Completed code (Exercise.c). 2. Report.pdf – Report.pdf should contain a section called Task 1 which should contain answers to the above asked questions for Part A and Part B. Note: Do not zip up the deliverables. Upload them separately. Task 2: Non-Executable Stack (50% of grade): This task is also divided into two parts, (A) Understanding the importance of non-executable stack, and (B) Experimenting with vulnerable code with protected and unprotected stack. The understanding part is worth 60% of this task (i.e., 30% of total grade of this project). The remaining 40% is for part B. Part A) Understanding Stack Protection (30% of grade): Review various mechanisms that are used to protect against buffer overflow exploits. More specifically, research the methods given below and write a brief explanation for each one of them. Each answer must be no more than a paragraph, and definitely no more than half a page of text (diagrams do not count to this limit).1. Stack smashing via buffer overflow. 2. Stack canary. 3. NX (Non-Executable Stack). 4. Address space layout randomization (ASLR).Part B) Experiments with execution of code (20% of grade):For this part of task 2, you need to locate the Stack_Protection directory via terminal, and there you will find vuln.c. You should review it carefully and then compile this source code into four different binaries with the following gcc options:• gcc -g -O0 -fno-stack-protector -z execstack -o vuln-nossp-exec vuln.c • gcc -g -O0 -fno-stack-protector -o vuln-nossp-noexec vuln.c • gcc -g -O0 -z execstack -o vuln-ssp-exec vuln.c • gcc -g -O0 -o vuln-ssp-noexec vuln.cTask 2 Part B Questions:(Each answer should be no more than a paragraph.) 1. Explaining the functionality of -fno-stack-protector and -z execstack options of gcc. Explain the differences you see in the binaries when the binaries are created with and without these options. 2. Which of the above four binaries can you exploit, by smashing the stack and overflowing a buffer? 3. Attempt to find the stack canary value in vuln-ssp-exec binary, by using a debugger like gdb. Does the canary value change or remain the same across multiple compilations/ executions? Post screenshots of your attempts. Deliverables for Task 2: 1. Report.pdf. The same Report.pdf should also contain a section – Task 2, which has your answers of the above asked questions in Task2, for Part A and Part B and screenshots/ diagrams if required. Note: Just a single Report.pdf for both Task1 and Task2! Good luck!
Computer Networks (CS 456) A Congestion-controlled Pipelined RDT Protocol over UDP Work on this assignment is to be completed individually Assignment Objective The goal of this assignment is to implement a Congestion-controlled Pipelined RDT protocol over UDP, which could be used to transfer a text file from one host to another across an unreliable network. The protocol should be able to handle network errors (packet loss), packet reordering, and duplicate packets. For simplicity, your protocol is unidirectional, i.e., data will flow in one direction (from the sender to the receiver) and the selective acknowledgements (SACKs) in the opposite direction. To implement this protocol, you will write two programs: a sender and a receiver, with the specifications given below. To test your implementation, we will provide a third program, the network emulator, that will emulate an unreliable network link.Packet Format All packets exchanged between the sender and the receiver should have the following structure:integer type; // 0: SACK, 1: Data, 2: EOT integer seqnum; // Modulo 32 integer length; // Length of the String variable ‘data’ String data; // String with Max Length 500Each integer field is a 4-byte unsigned integer in network byte order. The type field indicates the type of the packet. It is set to 0 if it is a SACK, 1 if it is a data packet, 2 if it is an end-of-transmission (EOT) packet (see the definition and use of an end-of-transmission packet below). For data packets, seqnum is the modulo 32 sequence number of the packet. The sequence number of the first packet should be zero. For SACK packets, seqnum is the sequence number of the packet being acknowledged. The length field specifies the number of characters carried in the data field. It should be in the range of 0 to 500. The data string should be exactly length bytes long. For SACK packets, length should be set to zero. A reference implementation of the packet format is provided to you as a Python 3 file named “packet.py”.Sender Program (sender) You should implement a sender program, named sender. Its command line input includes the following in the given order: • , • , • , • , and • Upon execution, the sender program should be able to read data from the specified file and send it using a congestion-controlled pipelined (selective repeat) RDT protocol to the receiver via the network emulator. The initial window size should be set to N=1 packet. After all contents of the file have been transmitted successfully to the receiver (and corresponding SACKs have been received), the sender should send an EOT packet to the receiver. The EOT packet is in the same format as a regular data packet, except that its type field is set to 2 and its length is set to zero. The sender can close its connection and exit only after it has received SACKs for all data packets it has sent and received an EOT from the receiver. To keep the project simple, you can assume that the EOT packet never gets lost in the network.To ensure reliable transmission and congestion control, your program should implement the congestioncontrolled pipelined (selective repeat) RDT protocol as follows:If the sender has a packet to send, it first checks to see if the window is full. If the window is not full, the packet is sent, the appropriate variables are updated, and a timer for the packet is started. The sender will use a timer per packet. If the window is full, the sender will try sending the packet later. When the sender receives an acknowledgement packet with seqnum n, it will be taken to be a selective acknowledgement, indicating that the packet with the sequence number n has been correctly received at the receiver. If a timeout occurs and the timer is associated with the packet that is at the base of the window, the sender sets N=1 (which causes the window to shrink and only contain the packet at the base) and retransmits that packet. Otherwise, if a timeout occurs and the timer is associated with any other packet, the sender sets N=1 (thereby shrinking the window and forcing the packet outside the window), and the packet’s retransmission is delayed until it re-enters the window. (Note: A packet can exit and re-enter the window within one timeout interval. A packet’s timer should not be reset upon exiting the window.) Once a packet is retransmitted, the timer of that packet is reset. If a new SACK (and not a duplicate SACK) is received, N is incremented by 1 up to a maximum of 10 (N cannot exceed 10). The first packet of the file must be transmitted with seqnum 0, the second packet with seqnum 1, and so on. After the packet with seqnum 31 is transmitted, the next packet is transmitted with seqnum 0. Output For both testing and grading purposes, your sender program should be able to generate three log files, named as seqnum.log, ack.log, N.log. Whenever a packet is sent, its sequence number should be recorded in seqnum.log. The file ack.log should record the sequence numbers of all the SACK packets and the EOT packet that the sender receives during the entire period of transmission (including duplicate/old SACKs). For EOT packets, the sequence number should be written to the file as “EOT.” N.log should record the initial value of N, as well as every time the value of N is updated. The format for these log files is one timestamp, space, and one sequence number per line. Timestamps are recorded as “t=X”, where X is the timestamp of the current action. The timestamp is a number that is incremented by one at every new event (i.e., a new packet to be sent, receiving a SACK/EOT, timeout, or delayed retransmission). The timestamp t=0 is reserved for initialization, and the only event that happens during this is the window size N being initialized to 1. Thus, N.log will have t=0 1 as the first line in the log. Packet transmissions begin at t=1. For the first packet, your program should write t=1 0 in seqnum.log for packet #0 sent at t=1. If an EOT is sent by the sender at t=105, then seqnum.log should record t=105 EOT. Similarly, if an EOT is received by the sender from the receiver at t=106, then ack.log should record t=106 EOT.Receiver Program (receiver) You should implement the receiver program, named as receiver, on a UNIX system. Its command line input includes the following in the given order: • , • , • , and • When receiving packets sent by the sender via the network emulator, the receiver should execute the following: • Check the sequence number of the packet. • If the packet is an EOT packet, send an EOT packet back and terminate the program. • Else, if the sequence is within the receiver window: o Send a SACK for the packet o If the packet was not previously received, add the packet to the buffer, then, if the received packet is at the base of the window, write the data in the packet and any previously buffered and consecutively numbered packets to the file and remove those packets from the buffer• Else, if the sequence number is within the last 10 consecutive sequence numbers of the base of the window o Send a SACK for the packet, then discard the packet • Otherwise, ignore the packet.Output Network Emulator (nEmulator) The network emulator is provided to you as a Python 3 program. When the emulator receives a data packet from the sender, it will discard it with the specified probability. Otherwise, it stores the packet in its buffer, and later forwards the packet to the receiver with a random amount of delay (less than the specified maximum delay). The same behaviour applies to SACKs received from the receiver. EOT packet from the sender is never discarded. It is forwarded to the receiver once there are no more data packets in the buffer. EOT packet from the receiver is also never discarded. It is forwarded to the sender once there are no more SACKs in the buffer.To run nEmulator, you need to supply the following command line parameters in the given order: • , • , • , • , • , • , • , • , • (Boolean: Set to 1, the network emulator will output its internal processing, one per line, e.g. receiving Packet seqnum /SACK seqnum, discarding Packet seqnum /SACK seqnum, forwarding Packet seqnum /SACK seqnum). Hints • You must ensure your programs run in the CS Undergrad Environment • Experiment with network delay values and sender time-out to understand the performance of the protocol. • To ensure the programs connect properly, you should run nEmulator, receiver, and sender in this order. Please ensure that your implementation works even if the three programs run on separate machines within the CS Undergrad Environment. Example Execution 1. On the host host1: nEmulator 9991 host2 9994 9993 host3 9992 1 0.2 0 2. On the host host2: receiver host1 9993 9994 3. On the host host3: sender host1 9991 9992 50 Procedures Hand in Instructions Submit all your files in a single compressed file (.zip, .tar etc.) using LEARN. The filename should include your username and/or student ID.You must hand in the following files / documents: • Source code files for your sender and receiver • Makefile (if applicable): if your program requires compilation, your code must compile and link cleanly by typing “make” or “gmake” • README file: this file must contain instructions on how to run your program, which undergrad machines your program was built and tested on, and what version of make and compilers you are using (if applicable). Documentation
Assignment 3 A Network on a Laptop Work on this assignment is to be completed individually 1) Objective The goal of this programming assignment is to get hands-on experience in computer networking by simulating a virtual network using Mininet. Mininet is a network emulator which creates a network of virtual hosts, switches, controllers, and links. This assignment will be an opportunity to comprehensively review the Internet Protocol (IP) and its forwarding fabric in a virtual Software Defined Network (SDN). Specifically, we will experiment with routing configurations and the OpenFlow protocol, which are the building blocks of a SDN. You will begin with installing Mininet and using Mininet’s Python API, implement a virtual network topology. Next, the switches in the virtual SDN will be configured to forward packets according to given rules and specifications. If the configurations are correct, the virtual hosts inside the virtual network will be able to communicate with each other. This assignment is divided into four parts: Part A, B, C, and D.2) Background You will find necessary background material in the following textbook chapter sections and articles: a. Chapter 4 Section 4.4 Generalized Forwarding and SDN b. Chapter 4 Section 4.5 Middleboxes c. Chapter 5 Section 5.5 The SDN Control Plane d. Mininet Documentation at http://mininet.org/overview/For this assignment, you will have to download a virtual box and virtual machine to run on the virtual box. 1. To download a virtual box, please download and install VirtualBox. 2. We have created a virtual machine for CS456 Computer Networking course, which includes the software needed to complete the assignment. Please download it from here, it will download as an .ova file. To run the virtual machine, double-click on the downloaded .ova file, which will open in VirtualBox. Complete importing the appliance, our virtual machine, without changing the default settings.Getting Started Quick setup guide assuming you have VirtualBox installed: 1. Start the provided VM in Virtualbox. 2. After the VM boots, you will see a screen with a password prompt for the user mininet. Enter mininet as the password. 3. In the CS456 VM provided for this course, you will find all CS456 related files in the directory /home/mininet/cs456-a3 4. Open a terminal by selecting Menu->System Tools -> MATE Terminal. 5. Enter sudo mn in the terminal, you should see the following output:The above output shows that Mininet has created a simple network topology with one switch and two hosts connected to it. Type exit, to exit the Mininet shell, then type sudo mn -c to clear the created topology.6. The VM comes with Open vSwitch and a controller pre-installed. Open vSwitch (OVS) is used for creating a programmable switch, i.e., a switch that works with flow table rules. The controller installs the rules in the network switches based on the network topology to ensure connectivity between hosts. Mininet uses OVS and a controller in its default network. To test whether the controller works, type sudo mn –test pingall in the vm terminal. You should see an output similar to the illustration below.Note the logs that state that Mininet is starting the controller. Also note that both hosts are reachable from one another according to the logs. Again, type in sudo mn -c to clear the created topology. 7. To see the effect of the controller, we will repeat the above command but ask Mininet to ignore the controller. Type in the command: sudo mn –test pingall –controller=noneYou should see an output like the one illustrated in the figure below.We see that Mininet gets stuck, while waiting for the switches to connect. This is because in the absence of a controller, the switches do not have forwarding rules and do not know how to forward any of the packets.For the first two parts of this assignment, Part A and Part B, we will be working without a controller, meaning that we will be adding static flow table entries to the switches manually, rather than having a controller do it. The objective is to learn about flow tables and forwarding rules.3) Part A: Hands on Mininet In this part, you will learn how to write OVS rules for forwarding packets in a custom topology. Mininet allows the simulation of arbitrary network topologies using a Python API. You will learn how to create a custom topology to run in Mininet using the API. You will also learn how to add static OVS rules to switches in a topology.In the CS456 VM provided for this course, you will find all CS456 related files for Part A in the directory /home/mininet/cs456-a3/part-A. For Part A, the files are, topology.py, mininet_topology_full.pdf and ovs_connect_h0h1.shRunning a Custom Topology The python file, topology.py uses the Mininet Python API to create a custom topology. A pictorial representation of the network created in topology.py is in mininet_topology_full.pdf.To run the custom topology file in Mininet using the command: sudo python topology_filename.pywhere topology_filename.py is the name of the topology file you need to run. You will see that running topology.py, will create 10 hosts and 10 switches in a Mininet shell.Use the commands below in the Mininet shell to explore the topology.mininet> nodes mininet> net mininet> dump mininet> linksThe Mininet shell also allows running commands from each node. Try the following commands for example: mininet> h1 ifconfig mininet> s1 ping s2When running the above commands, the mininet shell will infer that the first item (h0) is the name of the node on which to run the rest of the command (ping h1); it will, behind-the-scenes, enter that node’s bash in your stead.Furthermore, to access a specific node, you can use: xterm node_name In which node_name is the name of the node whose you are trying to access, e.g., h1, s1, etc. This will open a new terminal window inside the VM. Now, you can run any command, such as, ifconfig inside that window to see the interfaces of the corresponding node.Refer to the Mininet walk through for more Mininet commands.Adding OVS rules The python file we have created for you creates the topology but does not create the OVS rules for forwarding packets, therefore, there is no connection between the hosts. You can verify this by running the command h0 ping h1 inside the Mininet shell and comparing the result with the previous ping. You should note that h0 cannot ping h1. You can press Ctrl+C to kill the ping command, without terminating the Mininet VM.The shell script ovs_connect_h0h1.sh includes the necessary commands to enable OpenFlow version 13 and install the forwarding entries to Open vSwitches s0 and s1.The shell script has to be executed while Mininet is running the custom topology. Therefore, while mininet VM is running the custom topology, open, a new terminal window, and change directory (cd) to the directory /home/mininet/cs456-a3/part-A that contains the file ovs_connect_h0h1.sh, and run: sudo ./ovs_connect_h0h1.shGo back to the mininet shell and try h0 ping h1 again. You will see that the ping works. Try the ping in the opposite direction, does that work as well?Write a shell script, called partA_connect.sh to add the right flow entries in the appropriate switches to make sure that the following pairs of hosts, and only these hosts, can ping each other: h2 ↔︎ h4 h1 ↔︎ h6 h0 ↔︎ h3.4) Part B: Custom Topologies In this part, you will create a custom topology using the python API for Mininet. The sample custom topology of part A, topology.py, is a good starting point for learning how to create your own topologies. For Part B, you must create the topology illustrated in Figure 1 using Mininet, such that the host Alice and Carol can ping each other, but Bob should not be able to ping either Alice or Carol. Both the buses and routers are implemented by switches in Mininet. You will need to submit two files for this assignment – A python script: This will set up the topology depicted in the figure, with a L2 switch acting as a bus for each subnet (three switches for each of the three buses), and a switch acting as each of the routers (three switches for the three routers.) – A shell script: This will set the correct OVS rules in the three routers, such that Alice and Carol can ping each other, but Bob cannot ping either of them.Figure 1. Topology for Part B: Custom Topologies. The hosts are illustrated as square, the routers are shown as the virtual routers in purple and the black dot on them indicate a Network Interface Card (NIC).5) Part C: Introducing the Controller In this part, we explore the SDN controller and its value for configuring networks from a centralized component. In parts A and B, you have seen how configuring networks at a low level, even for achieving very simple requirements, can become complex and exhaustive.However, in real world, it is often not a human operator that comes up with those OpenFlow rules! The controller is a centralized software that acts as the brains of the SDN network. Using the SDN controller, you can instruct high-level policies, such as “host A should be able to ping host B”, and let the controller figure out how that translates to low-level OpenFlow commands and deploy it on the network switching devices. The controller is a server that will run in a separate terminal than the one you will use for Mininet commands. The CS456 VM you are provided with comes with a preinstalled POX controller.Follow the instructions below to run a topology connected to the POX controller: 2. Open a terminal, cd to ~/pox 3. Type and run the command below to start the POX controller and open its shell./pox.py –verbose py openflow.of_01 –port=6633 openflow.discovery forwarding.l2_learning host_tracker Note, that you will see the controller’s logs in this window after you run the mininet topology.4. Open a different terminal window, and run the following commandsudo mn –controller=remote,ip=127.0.0.1,port=6633 –topo=tree,depth=3 –mac –switch ovsThis will create a tree topology as illustrated below and connect it to the POX controller on port 6633 that was started in Step 3.Figure 2. A sample tree topology available in Mininet.5. In a new terminal window, you can explore the settings of a switch s1 and the flow rules on a switch s1 using the following commands:sudo ovs-ofctl show s1 sudo ovs-ofctl dump-flows s1The objective of this part of the assignment, is to explore the effect of the POX controller on the network by answering the following questions.1) Try pinging h5 from h1 (Type h1 ping h5 in mininet). The ping should succeed, even though you have not installed any OVS rules on the switches yourself. Study the output in the POX controller terminal. What has the controller done? Include a screenshot of the output as well as your interpretation of it. Make sure that the screenshot is readable. Hint: To interpret the effect of the controller, consider the path ping packets must take from h1 to h5. Now consider the relationship of the nodes depicted in the topology illustrated in Figure 2 and the dpid of the switches in the switch settings and the output of the POX controller.2) Take a screenshot of the ping RTT times for the first 5 ping messages. Compare the RTT of the first ping message with the subsequent ones. Is there a difference? Why or why not?3) Open a new terminal in the CS456 VM and dump the flow rules installed on switch s1 using the command, sudo ovs-ofctl dump-flows s1. Dump the flow rules on all the switches, make sure you change s1 in the command above to the appropriate switch name. Explore the flow rules installed in the switches before and after the initiating ping between hosts. Include a screenshot of the terminal showing all the dump commands and their outputs in your answer, use multiple screenshots, if necessary. The screenshots should be readable and clearly show which output pertains to which switch. Are the OVS rules like the rules you defined in part A? Do some switches have empty flow rule tables, even after the ping? If so, why? Briefly explain what kind of packet forwarding the switches achieve collectively.6) Part D: Middle Box A Middle Box is a real or virtual device that is placed inside the network and is used to perform some network function. A middle box network function might modify the network traffic passing through the middle box or passively collect information about it. For instance, a firewall is a network function that matches the traffic passing through it against a set of configured rules and filters out parts of the traffic e.g., dropping all traffic for a certain TCP port or allowing traffic only from certain IP addresses.In this part of the assignment, you will write a program to install the necessary OpenFlow rules to implement a simple middlebox. Rather than deploying a complicated middlebox like a firewall or a load-balancer that requires lots of configuration by systems administrators, we will deploy a very simple middlebox that will append the utf-8 encoded string “ from the middlebox” to the payload of all the packets it receives.In the CS456 VM provided for this course, you will find some of the CS456 related files for Part D in the directory /home/mininet/cs456-a3/partD. We will provide you with a program to send UDP packets in udp_client.py, the middlebox program cs456_middlebox.py, the custom topology cs456_tree_topology.py, and a UDP server program in udp_server.py so that you can test your code. The objective of this part of the assignment will be to use the POX SDN controller to install the OpenFlow rules necessary for your middlebox to work.Your program should be able to work in any loop-free network topology, that is, in any loop free network topology, you should be able to deploy the middlebox program, and use the UDP client program to send a message to the UDP server program and the message should have “ from the middlebox” appended to it by the time it reaches the UDP server.We have provided you with a skeleton file at /home/mininet/pox/pox/cs456/a3.py that you should use as a starting point for writing your controller program.Because your program needs to run within the POX controller framework, the steps for running your program will be different than that of a traditional python program. To run your program, you will first start POX and load the required modules.2. Open a terminal, cd to ~/pox 3. Run the following command: ./pox.py –verbose py openflow.of_01 –port=6633 openflow.discovery forwarding.l2_learning host_tracker cs456.a3This will start the POX command line where you can issue commands that run within the POX controller framework. Notice that we have loaded both the forwarding.l2_learning, the openflow.discovery and the host_tracker modules. The first, forwarding.l2_learningmodule turns every OpenFlow switch that connects to the controller into a MAC learning switch. This ensures that our ARP requests are switched through the network correctly. The openflow.discovery module enables the topology discovery features of the POX controller. In this way, an application can retrieve a graph of the network topology. A network graph reveals vital information about connectivity and reachability. We use it to compute the shortest path between the client node and the middlebox node and the middlebox node and the server node. The third module, the host_tracker, will keep track of the hosts in the network so that we can ask POX where the hosts are located and retrieve information about their MAC and IP addresses. For host tracking to work you always need to run pingall from the Mininet console, after you run the POX controller but before you test your code.Now that you are running the POX command line you can load all the symbols from the python module that you are working on by typing:from cs456.a3 import *To make the assignment simpler, your application will not need to set up the flow rules to implement the middlebox functionality in real time, instead you will use the command line interface to provide your program with the following parameters: • DPID of the switch that the client host is attached to. • DPID of the switch that the server host is attached to. • DPID of the switch that the middlebox host is attached to. • Source UDP port of the traffic • Destination UDP port of the traffic4. Your program will use this information, along with the POX APIs, to install the necessary flow rules to steer only the UDP traffic from the client host to the middlebox host and finally on to the server host. The middlebox host, should only receive the UDP traffic that matches the 4-tuple that defines the packet from the client host to the server host, with source UDP port and destination UDP port. The middlebox program should append the message “ from the middlebox” onto the payload of each of the UDP packets it receives and then transmits the augmented packet back out of its network interface.5. The POX controller must be programmed for the middlebox functionality we require. The file /home/mininet/pox/pox/cs456/a3.py provides the code necessary to program the POX controller. The install_udp_middlebox_flows function, which we have provided for you in the a3.py file, will print a message encouraging you to complete the assignment by adding code to this function. The skeleton file also contains some helper functions that should be useful in completing the assignment. The parameters and return values of each of the helper functions are documented within the source code. The install_udp_middlebox_flows function also contains some comments that will guide you in your completion of this part of the assignment.To run the program in your controller, type and execute the command below in the POX command line:install_udp_middlebox_flows(,,,source_port,destination_port)6. Testing Your Program. You are expected to test your implementation of install_udp_middlebox_flows using Mininet. As was mentioned earlier, your program is expected to work for in various loop-free network topologies so you should test with two or three different topologies. The mininet command line program can be used to automatically create a few different network topologies of various sizes. For example, to create a linear topology with 5 nodes and one host attached to each node run:sudo mn –mac –topo=linear,5 –controller=remote,ip=127.0.0.1,port=6633We will only use the bult in linear topology, with differing number of hosts, to evaluate your submission. However, for testing we have provided an additional custom topology. The topology is a tree topology where the branching factor of the tree is always two and there is a host connected to every node in the tree. You can instantiate this custom topology using the command:sudo mn –mac –custom /home/mininet/cs456-utils/cs456_tree_topology.py –topo=SimpleTreeTopo,3 –controller=remote,ip=127.0.0.1,port=6633Once you have started Mininet you need to start the middlebox program on the middlebox host that you have chosen and the server program on the server host that you have chosen.Finally, you need to follow the steps described in step 5 to run install_udp_middlebox_flows with the DPID’s that correspond to your client, server and middlebox hosts. All the programs that are to be run on the hosts in the network are in /home/mininet/cs456-a3/part-D directory and will tell you the parameters they need if you invoke them with the –help flag.You can start an xterm session on the client, middlebox and server hosts from the Mininet terminal and run the appropriate programs from the /home/mininet/cs456a3/part-D directory with the correct parameters to transmit a message from client host to server host. The controller program you wrote should install the appropriate flow rules to enable the middlebox functionality that is required for Part D of this assignment. The expected result is that for every UDP packet sent from client host with source port, the server host should print a log line with the message that was sent appended with the phrase “ from the middlebox.”7) Tips and Tricks • Always assume that there is exactly one host connected to every switch. This assumption is easy to realize in practice by using either the Mininet linear topology or the custom tree topology that has been provided for you. • Some documentation for Pox is available at https://noxrepo.github.io/pox-doc/html/. If you’re wondering how to do something with the Pox API, you can usually find the answer on this page. o Run the Mininet VM GUI and start an instance of Mininet using the desktop of the VM. This is important because there is no way to start shells on the mininet hosts without an X server (i.e., if you are SSHing to the VM rather than using the GUI) o To actually write the necessary code to complete the assignment and to run POX, SSH to the Mininet VM and work in the terminal, this will let you avoid dealing with a possibly sluggish VM GUI. o We have already setup the CS456 VM to enable SSH, you can run ssh on your local machine, by opening a terminal or through putty, to remotely login to the CS456 VM by running the ssh command belowssh -p40000 [email protected]o If you prefer using a GUI text editor to write your code, you can set up a shared folder on the VM so that you will be able to access files on the VM from your host computer and edit them locally. For help setting up a shared folder, see shared folder setup (you can ignore the parts about installing the VirtualBox guest additions, we’ve done that for you already). • For Part D of the assignment, you are not allowed to use OpenFlow to modify any of the traffic passing through the switches. Instead, your program should steer traffic destined for the server host to the middlebox host before the modified traffic is steered to the server host. The only modification of the traffic sent by the client with the same UDP source port will be done by the middlebox program. • When you are debugging your implementation, remember that you can use ovs-ofctl to inspect the flow tables of the switches in the network.8) Deliverables 1) For Part A there are two deliverables: 1) The file partA.md, which explains what each field name in the first add-flow command in the provided file means. Each field should be explained in no more than one sentence.2) submit a file named partA_connect.sh, which includes the OVS commands that enable only the following pairs of hosts to ping each other and only each other: h2 ↔︎ h4 h1 ↔︎ h6 h0 ↔︎ h3OVS routing entries and comments similar to those provided to you in the walkthrough.2) For Part B, there are two deliverables: 1) submit the Python code for implementing the topology for Part B, in a file named partB_topology.py.2) The shell script partB_connect.sh that allows for the connection of hosts as described in part B.3) For Part C, there is one deliverable, a file named partC.pdf that clearly answers the three questions asked in part C, by including explanations that are justified by one or more of the required screenshots.4) For Part D, there is one deliverable, your completed /home/pox/pox/cs456/a3.py file.9) Instructions for SubmissionYou must hand in the following files / documents: • Source code files: partB_topology.py and a3.py • Shell script files: PartA_connect.sh and partB_connect.sh • Written answers: in partA.md and partC.pdf10) Additional Notes a. Be clear about all the questions that you are answering, keeping answers brief and concise while including all the required information. b. For answering the OpenFlow questions in Parts A and B, make sure that shell scripts containing the OVS commands work. The shell scripts will be tested and expected to provide the appropriate connectivity. c. The python and shell scripts are expected to run seamlessly in the VM provided for the course. You do not need any additional dependencies for parts A, B and D. In case you must, provide the installation guides in a file readme_partX.md where X is replaced by A, B or D. It is your responsibility to make sure the installation guide is clear and brief. d. Using the Markdown syntax in the answer files is not required but encouraged.11) Grading RubricRubric Item Scenario Description Failure Penalty Part A: Hands on Mininet (15%) 1 Question A-I: Explain the meaning of the fields in one rule, explain the meaning of the rule 2% 2 Question A-II: The connections between pairs being set up by running the shell script 6% 3 Question A-II: The remaining pairs remaining disconnected after running the shell script (should only be granted if the previous item works) 4% 4 Question A-II: the shell script is clear, easy to read and well documented. 3% Part B: Custom Topologies (35%) 5 Question B-I: Correct specification of the network links and topology 10% 6 Question B-I: Correct specification of the hosts and IP assignments 8% 7 Question B-II: Working ping between Alice and Carol 10% 8 Question B-II: Alice and Bob must remain disconnected, should only be granted to those who have implemented the previous one 7% Part C: Introducing the Controller (15%) 10 Question C-I: Correct controller logs 2% 11 Question C-I: Explaining what the controller is doing 3% 12 Question C-II: Ping output and observation 2% 13 Question C-II: RTT difference justification 3% 14 Question C-III: Correct flows from all switches 3% 15 Question C-III: Explaining the collective effect of the installed flows concisely in simple language 2% Part D: Middle Box (30%) 16 D-I: Flow rules are correctly implemented for the linear topology 15% 17 D-II: Code Inspection 15% General: Code readability, documentation and inspection 5%
Assignment Objective The goal of this assignment is to implement a congestion controlled pipelined Reliable Data Transfer (RDT) protocol over UDP, which could be used to transfer a text file from one host to another across an unreliable network. The protocol should be able to handle packet loss, packet reordering, and duplicate packets. For simplicity, your protocol is unidirectional, i.e., data will flow in one direction (from the sender to the receiver) and the acknowledgements (ACKs) in the opposite direction. To implement this protocol, you will write two programs: a sender and a receiver, with the specifications given below. To test your implementation, we will provide a third program, the network emulator, that will emulate an unreliable network link.Packet Format All packets exchanged between the sender and the receiver should have the following structure:integer type; // 0: ACK, 1: Data, 2: EOT integer seqnum; // Modulo 32 integer length; // Length of the String variable ‘data’ String data; // String with Max Length 500Each integer field is a 4-byte unsigned integer in network byte order. The type field indicates the type of the packet. It is set to 0 if it is an ACK, 1 if it is a data packet, 2 if it is an end-of-transmission (EOT) packet (see the definition and use of an end-of-transmission packet below). For data packets, seqnum is the modulo 32 sequence number of the packet. The sequence number of the first packet should be zero. For ACK packets, seqnum is the sequence number of the packet being acknowledged. The length field specifies the number of characters carried in the data field. It should be in the range of 0 to 500. The data string should be exactly length bytes long. For ACK packets, length should be set to zero. A reference implementation of the packet format is provided to you as a Python 3 file named “packet.py”.Sender Program (sender) You should implement a sender program, named sender. Its command line input includes the following: , , , , and in the given order.Upon execution, the sender program should be able to read data from the specified file and send it using the congestion controlled RDT protocol to the receiver via the network emulator. The initial window size should be set to N=1 packet. After all content of the file has been transmitted successfully to the receiver (and corresponding ACKs have been received), the sender should send an EOT packet to the receiver. The EOT packet is in the same format as a regular data packet, except that its type field is set to 2 and its length is set to zero. The sender can close its connection and exit only after it has received ACKs for all data packets it has sent and received an EOT from the receiver. To keep the project simple, you can assume that the end-of-transmission packet never gets lost in the network.To ensure reliable transmission and congestion control, your program should implement the congestion controlled pipelined RDT protocol as follows:If the sender has a packet to send, it first checks to see if the window is full, that is, whether there are N outstanding, unacknowledged packets. If the window is not full, the packet is sent, the appropriate variables are updated, and a timer is started if not done before. The sender will use only a single timer that will be set for the oldest transmitted-but-not-yet-acknowledged packet. If the window is full, the sender will try sending the packet later. When the sender receives an acknowledgement packet with seqnum n, the ACK will be taken to be a cumulative acknowledgement, indicating that all packets with a sequence number up to and including n have been correctly received at the receiver. If a timeout occurs, the sender sets N=1 and retransmits the packet that caused the timer to timeout (only that one packet and not all the non-ACKed packets). If a packet is retransmitted, the timer is reset. If a new ACK (and not a duplicate ACK) is received, but there are still additional transmitted-but-yet-tobe-acknowledged packets, the timer is restarted. If there are no outstanding packets, the timer is stopped. Also, if a new ACK is received, N is incremented by 1 up to a maximum of 10 (N cannot exceed 10). The first packet is transmitted with seqnum=0, the second packet is transmitted with seqnum=1, and so on. After the packet with seqnum=31 is transmitted, the next packet is transmitted with seqnum=0. Output For both testing and grading purposes, your sender program should be able to generate three log files, named as seqnum.log, ack.log, N.log. Whenever a packet is sent, its sequence number should be recorded in seqnum.log. The file ack.log should record the sequence numbers of all the ACK packets that the sender receives during the entire period of transmission. For EOT packets, the sequence number should be written to the file as “EOT”. N.log should record the initial value of N, as well as every time the value of N is changed. The format for these log files is one timestamp, space, and one sequence number per line. Timestamps are recorded as “t=X”, where X is the timestamp of the current action. The timestamp is a number that is incremented by one at every new event (i.e., a new packet to be sent, receiving an ACK, or timeout). The timestamp t=0 is reserved for initialization, and the only event that happens during this is the window size N is initialized to 1. Thus, N.log will have t=0 1 as the first line in the log. Packet transmissions begin at t=1. For the first packet, your program should write t=1 0 in seqnum.log for packet #0 sent at t=1. If an EOT is sent by the sender at t=105, then the log should record t=105 EOT. Similarly, if an EOT is received by the sender from the receiver at t=106, then the log should record t=106 EOT.Receiver Program (receiver) You should implement the receiver program, named as receiver, on a UNIX system. Its command line input includes the following: , , , and in the given order.When receiving packets sent by the sender via the network emulator, it should execute the following: • Check the sequence number of the packet. • If the sequence number is the one that it is expecting: o If the packet is an EOT packet, send an EOT packet back and terminate the program. o Otherwise, write the data from the packet to the output file. o Then check if the packet with the next sequence number is in the buffer. o If the packet exists, remove the packet from the buffer, write the data of the packet to the output file, then repeat the previous step. o If the packet does not exist, send an ACK packet back to the sender with the seqnum equal to the seqnum of the last packet written to disk and set the expected seqnum to the seqnum of the missing packet. • Otherwise, if the sequence number is not the one that it is expecting: o If the sequence number is within the next 10 sequence numbers, store the received packet in a buffer if the packet is not already stored. o In all other cases (e.g., duplicate/old packet), discard the received packet. o For both the cases above, send an ACK packet for the most recently received in-order packet. Once the receiver has received all data packets and an EOT from the sender, it should send an EOT packet then exit. Output Network Emulator (nEmulator) The network emulator is provided to you as a Python 3 program. When the emulator receives a data packet from the sender, it will discard it with the specified probability. Otherwise, it stores the packet in its buffer, and later forwards the packet to the receiver with a random amount of delay (less than the specified maximum delay). The same behaviour applies to ACKs received from the receiver. EOT packet from the sender is never discarded. It is forwarded to the receiver once there are no more data packets in the buffer. EOT packet from the receiver is also never discarded. It is forwarded to the sender once there are no more ACKs in the buffer.To run nEmulator, you need to supply the following command line parameters in the given order: • , • , • , • , • , • , • , • , • (Boolean: Set to 1, the network emulator will output its internal processing).Hints • The protocol is somewhat similar to a simplified version of TCP but it is not TCP! Notably, we do not implement fast retransmit, we buffer out-of-order packets, and sequence/ACK numbers have different. • You must ensure your programs run in the CS Undergrad Environment • Experiment with network delay values and sender time-out to understand the performance of the protocol. • To ensure the programs connect properly, you should run nEmulator, receiver, and sender in this order. Please ensure that your implementation works even if the three programs run on separate machines within the CS Undergrad Environment. Example Execution 1. On the host host1: nEmulator 9991 host2 9994 9993 host3 9992 1 0.2 0 2. On the host host2: receiver host1 9993 9994 3. On the host host3: sender host1 9991 9992 50 Procedures Hand in Instructions Submit all your files in a single compressed file (.zip, .tar etc.) using LEARN. The filename should include your username and/or student ID.You must hand in the following files / documents: • Source code files. • Makefile (if applicable): your code must compile and link cleanly by typing “make” or “gmake”. • README file: this file must contain instructions on how to run your program, which undergrad machines your program was built and tested on, and what version of make and compilers you are using (if applicable). Your implementation will be tested on the machines available in the undergrad environment. Documentation
Overview In this lab, your robot will be tasked with supervising a warehouse. The robot will have to map out its environment (using a lot of the same algorithms you have employed throughout the class), while avoiding obstacles (walls). If an obstacle is hit, the run is terminated. Your goal is to visit all of the five landmarks within 6 minutes (360 seconds). All the important files are present under the folder controllers/exploration_controller/. Specifically, focus on controllers/exploration_controller/exploration.py file. Exploration task Map Layout The map is organized as an occupancy grid, where each cell in the grid is either labeled “free”, “obstacle”, or “landmark”. In addition, every cell in the map starts out as unexplored (grey area), and as grid cells enter the robot’s field of vision, the cells are detected by the robot’s sensors and should be marked as explored. Localization Planning You will implement the frontier_planning() as well as the exploration_state_machine() functions in controllers/exploration_controller/exploration.py in order to traverse the map and visit all of the landmarks. Your frontiers are the unexplored cells in the map that are adjacent to the explored cells, and your algorithm should move to the centroid of the frontiers. Local Testing: Make sure to take advantage of functions in utils.py and remember that your run for either phase will terminate if you collide with an obstacle. Grading Rubric Autograder will grade your exploration on 10 maps. Submission Materials Submit your exploration.py file to gradescope. If you relied significantly on any external resources to complete the lab, please reference these in the submission comments. Running with Webots Once the exploration.py is complete, you can validate that your algorithm works with the WeBots simulator. 1. Open exploration_controller.py and ensure that the maze_name (line: 255) is set to the map you would like to test on. The map names are “maze1”, “maze2”, and “maze3”. A working implementation should work on all three maps. 2. Launch WeBots. Click File > Open World, then navigate to the “worlds” subfolder. Open the .wbt file which matches the maze_name from step 1. 3. A GUI window should appear which shows your exploration code running in a simple 2D approximation of the world to find a path. Then, the robot in WeBots should start moving along this path. a. We recommend selecting the “DEF e-puck Robot” object via the sidebar in the top-left of the WeBots screen. This will allow you to see the coordinate frame of the robot while it moves through the maze. b. Note that the 2D GUI window should automatically close after the robot is done moving. c. Also, the webots execution takes significantly longer time to run compared to GUI and autograder version. Examples (Robot-GUI) Robots should navigate towards the frontierRobot can use RRT to get around the obstacleBlue dot signifies the goal point Dotted line signifies the path to the next waypoint in the RRT path
The objective of this lab is to implement and test robot path planning capabilities, specifically the RRT algorithm. You will first implement the RRT algorithm, then apply it to drive a 2D robot in the WeBots simulation environment from start to goal configurations. In this lab, we assume that the obstacles and map are known ahead of time.All the code you have to implement is in the controllers/rrt_controller subfolder. Specifically, look for the files controllers/rrt_controller/map.py and controllers/rrt_controller/rrt.py.Part 1 – Basic RRTPlease complete the following helper functions in controllers/rrt_controller/map.py.• is_inbound() • is_inside_obstacle() • node_generator() • step_from_to()To test these helper functions, we have given you a local autograder. This should be much faster to run locally than on Gradescope. To run the autograder, navigate to the controllers/rrt_controller subfolder, then run python3 autograder.py helpersAfterwards, complete the RRT method in rrt.py, which handles the main loop of the algorithm. We provide code to limit the maximum number of nodes generated and terminate the loop once a path to goal has been found. Use your helper functions to implement the rest of RRT. Again, you can test this locally with python3 autograder.py rrtOnce the above steps are complete, you can validate that your RRT algorithm works with the WeBots simulator. (More detailed steps are on the next page.)1. Open rrt_controller.py and ensure that the MAP_NAME constant at the top is set to the map you would like to test on. The maps are named maze1, maze2, and maze3 (e.g. “./maps/maze2.json”). A working implementation should work on all three maps. 2. Launch WeBots. Click File > Open World, then navigate to the “worlds” subfolder. Open the .wbt file which matches the MAP_NAME from step 1. 3. A GUI window should appear which shows your RRT code running in a simple 2D approximation of the world to find a path. Then, the robot in WeBots should start moving along this path. a. We recommend selecting the “DEF e-puck Robot” object via the sidebar in the topleft of the WeBots screen. This will allow you to see the coordinate frame of the robot while it moves through the maze. b. Note that the 2D GUI window should automatically close after the robot is done moving.Figure 1. The WeBots world maze2 with the coordinate frame of the e-puck robot selected.Part 2 – Path SmoothingOnce again, you can test your implementation with the WeBots simulator, which will follow the same procedure detailed above.To test this part, you can use the same local autograder. This should be much faster to run locally than on Gradescope. To run the autograder, navigate to the controllers/rrt_controller subfolder, then run python3 autograder.py smoothingGrading: Your grade will come from the autograder running your code on the three maps you are given, plus three hidden maps which are different than the hidden ones.The exact point breakdown is as follows:Helpers is_inbound() 5 pts is_in_obstacle() 5 pts step_from_to() 10 pts Full RRT implementation RRT, autograded with 6 maps (3 hidden), 10 points per solved map 60 pts Path Smoothing Path smoothing, autograded with unsmoothed trajectories given 20 ptsSubmission: Submit the files rrt.py and map.py to Gradescope. If you relied significantly on any external resources to complete the lab, please reference these in the submission comments.
