Description You will be creating forms, view functions, and finishing templates for adding an account system to the project 3 app. For this website, users will have to be logged in in order to add comments. Also, we can see all the comments made by each user by going to their user-detail page. There will be two opportunities for extra credit: making the layout of the project nicer, and just adding more features to the website in general. Setup The setup of the API key should be complete from project 3. Activate your virtual environment Then, to install the necessary packages, run pip install -r requirements.txt. This week we’ll be using the – requests – Flask – Flask-MongoEngine (with Pillow) – Flask-WTF – Flask-Bcrypt – Flask-Login python-dotenv libraries Project This is the p4/ directory structure To run this project, stay in the p4/ directory and use the flask run command. The file that is run is run.py. It simply imports the app object from the flask_app/ package. The reason we have this new structure is to avoid the problem of circular imports in Python projects. The initialization of the app object and the other libraries happens in __init__.py. All of the view functions are in routes.py. The database models are in models.py, and the MovieClient class is now in client.py. The current_time() function you used in the last project is now in utils.py, and it’s been imported into routes.py for your convenience. Forms are still in forms.py. Make sure to set the secret key in __init__.py!!! routes.py There are five new template files, corresponding to five new view functions in routes.py. account.html login.html register.html user_detail.html 404.html Now we’ll go into detail about each of the new view functions: 1. account() – Login required Should be routed at /account. Renders the account.html template. The template has spaces for a greeting to the user, a username update form, a profile picture update form, and a link to see all of the current user’s reviews. In the account() view function, make sure you create the username update form, properly modify the current user’s username permanently if they change it to a name that’s not taken (commit change to database). For the greeting, you can choose how to greet the current user. It should use the current user’s username to greet them. (Hint: the current user object is available in every template). Also, display the current user’s profile picture. The forms should be rendered using Bootstrap classes. You can see an example of how we did that in movie_detail.html. If they do not have a profile picture, that’s okay. A profile picture is not required for every user. Make sure the profile picture updating form works whether or not the user has an existing profile picture or not. There should be a link to all of the current user’s reviews, pointing to the user detail page of the current user. 2. login() Should be routed at /login. Renders the login.html template. The template has spaces for adding a message to the user telling them to register (if they don’t have an account), for displaying a login form, and for showing flashed messages (messages created with flash() function). For the login() view function, redirect the user away from the page if they’re already authenticated (they don’t need to see the login page, then). Add the LoginForm and properly authenticate the user. If they’re not successfully authenticated, ask the user to login again (don’t give them hints whether the username or password was wrong). If they are successfully authenticated, redirect to their /account page. In login.html, ask the user to register if they don’t have an account (and provide the link for them to do so), and display flashed messages, the login form, and any login form errors rendered with Bootstrap classes. 3. register() Should be routed at /register. Renders the register.html template. The template has spaces for asking the user to login if they already have an account, for showing the registration form, and for showing flashed messages. For the register() view function, redirect the user away from the page if they’re already authenticated. Add the RegistrationForm and create the new account for the user if the form is validated (make sure to store hashed passwords, not plaintext). If any errors occur with registration, display the error message to the user. If successfully registered, redirect the user to the /login page. In register.html, ask the user to login if they already have an account, and provide the link for them to do so, display any messages you want flashed, and display the registration form, all rendered with Bootstrap. 4. user_detail(username) Should be routed at /user/. Renders the user_detail.html template. The template has a space for indicating whose reviews we’re looking at, a space for showing their profile picture, a space for displaying all reviews, and a space for showing any errors. In the user_detail() view function, if the specified user exists, then render all of the reviews written by that user. If they don’t exist, display an error message. In user_detail.html, indicate which user’s reviews we’re looking at. This is best done with their username. Then under that, display all of the reviews they’ve made. You should indicate how many reviews the specified user has made in total, and then for each review show: – When the review was created – Which movie the review was made for (movie title) – The review content itself. Your template should be able to handle a variable number of reviews. 5. logout() – Login required Should be routed at /logout. Doesn’t render a template, but logs out the current user. Redirect to the /index after logging out. 6. movie_detail() On the movie_detail() page, where users can enter reviews, show each commenter’s profile picture next to their review. Notice that to get the profile picture associated with the reviewer for each review, we call {{ review.image }}. We thought this was the simplest way to implement our solution. After retrieving the correct reviews from Mongo, we just added an image item and passed it to the template. You are allowed to change this implementation. 7. custom_404() Add a custom 404 page. The barebones custom_404() function is provided. You should add the necessary decorators and other functionality to this function in order render a custom 404 page. You have to add the HTML/Jinja code to create the custom page. It must include the website header, a message informing the user about the 404 error, and include a link back to the index page. Additionally, for each view function for which we indicated login required, use the login_required() decorator from Flask-Login. Profile pics forms.py In forms.py, we’ve included the code for the RegistrationForm since we already discussed the implementation in class. We modified the MovieReviewForm since users no longer have to enter their name; it automatically gets added, since they’re logged in when they’re adding a review. You have to implement the LoginForm, UpdateUsernameForm, and UpdateProfilePicForm. 1. LoginForm – Should have username, password, and submit fields. For the password, use a PasswordField. Use validators that check that data has been entered, and create custom validator(s) if needed (examples can be seen in the slides for wk3 and in RegistrationForm). 2. UpdateUsernameForm – Should have fields for username and submitting data. The new username should also be between 1 and 40 characters long. If the username is taken, then warn the user, either by using a flashed message or a custom validator in the form itself. 3. UpdateProfilePicForm – Should have a FileField that only allows images of types jpg and png, and a submit field. A user is not required to have a profile picture. Make sure you handle the cases where a user uploads their first profile picture and where they are replacing an existing profile picture. models.py In models.py, you have to implement the User and Review document models. You also have to implement the user loader function, which is used by Flask-Login in order to retrieve the current user object. 1. User – Should have these fields: – A required and unique username field, with minimum length 1 and maximum length 40 characters. – A required and unique email field – A required password field (only store slowhashed passwords!) – An optional profile_pic field – (Optional) Any fields you’d like to add that you think will make your app easier to implement. You should also implement the get_id() method of User, which returns a string unique to each user, so that Extra Credit There are two opportunities for extra credit: 1. You can improve the layout and look and feel of the website by editing any the templates or the custom.css file. You can also try improving the accessibility of the website. If you believe you should receive extra credit for your visual additions, edit extra_credit.md with brief and complete descriptions of the visual changes you made and how we can see them. 2. Adding more features to the website in general is another item you can receive extra credit for. Some ideas include watch lists, favorite lists, recentlyreviewed movies page, top-rated movies page, etc. If you believe you should receive extra credit for any extra features you implement, edit extra_credit.md with brief and complete descriptions of the additions you made how we can see them. We’ll give up to 20% extra credit for each opportunity, so there’s a total opportunity for 40% extra credit. Testing When your current directory is p4/, you can run the command flask run in your terminal or command line to see your website. This will use the run.py file. We’ve listed all the requirements above, in high detail. Make sure you fill out all of those requirements, and that you display errors relevant to each page properly, and that the current_user object is used where needed. We will be releasing a set of demo videos within the next couple of days. Submissions Assure that you’ve tried out all the different things that could go wrong and that they are behaving appropriately (and the things that are supposed to work, still do), and errors are shown when they are supposed to be shown. For submission, submit the zipped p4/ directory. The directory, along with its contents, should be zipped, not the contents of the directory. In other words, when we unzip your file, we should see the p4/ directory. If you have any questions on how to submit, please post on Piazza. After zipping, submit the zip file to the appropriate ELMS page. Grading No test results will be shown. If you don’t use MongoDB, you will get a 0 on this project. Your project will be graded on (1) correctness and (2) robustness. Here are the correctness requirements: Correctness: These requirements include requirements from project 3 as well as functionality we implemented. Since this project is an extension of project 3 where we’re adding user management, the provided functionality still has to work properly. All of these features have already been implemented. This rubric item is for you to make sure that the functionality we gave you is still working after you add your changes. | Requirement | Points | | ———————————————————————————- | —— | | Reviews are shown per movie (unique per movie) | 15 | | Queries are shown when media is searched up | 15 | | Reviews are persisted through app lifetime | 15 | | Reviews are persisted when app is closed and restarted (across multiple lifetimes) | 15 | | Provided forms have the correct names and validators | 10 | | Provided form rendering works, errors shown when validation fails | 10 | | MovieReviewForm has multi-line input for review | 5 | | Show reviews for movie after form submitted successfully. | 5 | | Forms requiring login only shown when logged in | 10 | | Page header changes links properly based on whether user is logged in | 10 | These requirements are 110 points New project 4 requirements: | Requirement | Points | | ——————————————————————————— | ———– | | Secret key set | 2 | | UpdateUsernameForm works according to the specifications | 15 | | UpdateProfilePicForm works according to specifications | 15 | | Profile pictures seen on account, user detail, and movie detail pages. | 15 (5 each) | | Views that require login, do require login | 10 | | Account page has greeting and link to current user’s reviews | 5 | | User detail page lists all reviews, all other necessary information/functionality | 20 | | Log-in functionality works, contains necessary elements | 20 | | Registration functionality works, contains necessary elements | 20 | | Logout works | 3 | | Custom 404 page implemented, contains necessary elements | 10 | | Logged-in users redirected away from login and registration pages | 10 | | The three forms you implement have the correct names and validators | 15 (5 each) | | Form fields are rendered with Bootstrap, errors are shown when validation fails | 10 | | User loader function implemented | 5 | | User class has all necessary fields with correct validators | 15 | | Review class has all necessary fields with correct validators | 15 | These requirements are 205 points. In total, there are 315 points. Robustness: Refer to the syllabus for the robustness requirement for all projects. The syllabus has been updated with this information, since it will be common to all projects.
In this project, you are going to use SimpleScalar as the evaluation engine to perform a design space exploration, using the provided framework code, over a 18-dimensional processor pipeline and memory hierarchy design space (some of these dimensions are not independent). You will use a 5-benchmark suite as the workload. You should use CSE Linux Lab machines (i.e. e5-cse-135-01.cse.psu.edu through e5cse-135-38.cse.psu.edu). We will test your results on those machines. To connect to these machines remotely, you should install VPN on your computer and then use ssh to connect to one of the machines. For more details, please refer to the CSE Student Lab access information. 1. Project Goal Your assignment is to, with an evaluation count limit of 1000 design points, explore the design space in order to select the best performing design under a set of two different optimization functions. These include: 1. The “best” performing overall design (in term of the geometric mean of normalized execution time normalized across all benchmarks) 2. The most energy-efficient design (as measured by the lowest geometric mean of normalized energy-delay product [units of energy delay product are joule-seconds] across all benchmarks) 2. Background 2.1. SimpleScalar SimpleScalar is an architectural simulator which enables a study of how different processor and memory system parameters affect performance and energy efficiency. The simulator accepts a set of system design parameters and an executable (workload) to run on the described system. A wide range of system statistics are recorded by the simulator as the executable runs on the simulated system. Once the framework in this project is setup, interested readers can have a look at one of the log files in rawProjectOutputData folder to view SimpleScalar output. This project heavily uses SimpleScalar but most of the interface is abstracted out by a simpler framework interface. Nevertheless, you can refer to this SimpleScalar guide for details about parameters passed to SimpleScalar. 2.2. Design Space Exploration Given a set of design parameters, Design Space Exploration (DSE) involves probing various design points to find the most suitable design to meet required goals. Follow this quick reading about DSE before moving ahead. An exhaustive DSE simply tries out all possible combinations of parameter values to find the absolute best design. However, as the size of design space increases this approach quickly becomes infeasible. Consider a 10-dimensional design space with 5 possible values for each parameter and 2 minutes simulation time to evaluate a given design point; an exhaustive search will take 510 ∗2min ≈ 37years. A more intelligent DSE employs heuristics to intelligently prune down the design space and to prioritize evaluation of more reasonable design points first. If the assumptions employed by the heuristics are correct, the DSE will still result in the best design. On the other hand. with a set of reasonably justified assumptions a heuristic can result in a “good enough” design point. 2.3. Energy-Delay Product Energy-Delay Product (EDP) is a metric which consolidates both performance and energy efficiency. EDP = total execution energy * execution time Design A takes 100pJ to process an image in 100ms, EDP = 10000 units. Design B takes 80pJ to process an image in 2000ms, EDP = 160000. Design A is clearly more energy efficient, but it performs poorly as it incurs more execution time. EDP enables a more holistic design comparison. 3. Our Heuristic We define OurHeuristic as follows: 1. Design space dimensions can be labelled as either explored and unexplored. 2. Initially all dimensions are unexplored 3. Choose an unexplored dimension, exit if all dimensions are explored 3.1. Evaluate all possible design points by changing the value of this dimension only 3.2. Fix value of this dimension by selecting the best design so far (consider DSE goal) 3.3. Mark this dimension as explored 4. Go to step 3. You should choose an unexplored dimension in step 3 based on your PSU ID Numbers of students in the group, as follows. DSE dimensions can be categorized in four major classes as follows: 1. Branch predictor (BP) configurations (i.e. branchsettings, ras, btb) 2. Cache configurations (i.e. {l1, ul2}block, {dl1, il1, ul2}sets, {dl1, il1, ul2}assoc) 3. Core configurations (i.e. width, scheduling) 4. Floating Point Unit (FPU) configuration (i.e. fpwidth) Based on your PSU ID numbers, you should calculate (PSU ID Number 1+PSU ID Number 2) mod 24 and then you should look at the Table 1 and start from the first category in the corresponding row, and then second category, and so on. For example, if your PSU ID numbers are 9123456789 and 9111111111, the remainder of its sum’s division by 24 is 12 and you should explore Core configs first, then BP configs, then Cache configs, and then FPU configs at last. (If you are doing the project individually, consider the second student’s PSU ID as zero in your calculations.) 4. Logistics The set of possible points within the design space to be considered are constrained by the provided shell script wrapper runprojectsuite.sh. All allowed configuration parameters for each dimension of the design space are briefly described in the provided shell script. runprojectsuite.sh shell script takes 18 integer arguments, one for each configuration dimension, which expresses the index of the selected parameter for each dimension. All reported results should be normalized against a baseline design with configuration parameters which already hard-coded in the framework. Note that not all possible parameter settings represent a valid combination. One of your tasks will be to write a configuration validation function based upon restrictions described later in this document. Further, note that this design space is too large to efficiently search in an exhaustive manner. Hence, a heuristic will be developed to specify an order in which the design space will be explored. The framework code will evaluate a fixed number of design points per run. This parameter cannot be changed. The key part of your task in this project is to implement a heuristic search function that selects the next design point to consider, given either a Table 1. Exploration Orders based on PSU ID. (PSU ID Number Sum) mod 24 1st 2nd 3rd 4th 0 BP Cache Core FPU 1 BP Cache FPU Core 2 BP Core Cache FPU 3 BP Core FPU Cache 4 BP FPU Cache Core 5 BP FPU Core Cache 6 Cache BP Core FPU 7 Cache BP FPU Core 8 Cache Core BP FPU 9 Cache Core FPU BP 10 Cache FPU BP Core 11 Cache FPU Core BP 12 Core BP Cache FPU 13 Core BP FPU Cache 14 Core Cache BP FPU 15 Core Cache FPU BP 16 Core FPU BP Cache 17 Core FPU Cache BP 18 FPU BP Cache Core 19 FPU BP Core Cache 20 FPU Cache BP Core 21 FPU Cache Core BP 22 FPU Core BP Cache 23 FPU Core Cache BP performance, or an energy efficiency goal. Note that the framework code must be run once for each of the optimization function options. The framework, as given, provides functionality to enforce several, but by no means all, of the validation constraints. It is your job to implement validation functions to enforce constraints described throughout this document. 5. Framework A sample run to use the provided framework can look something like this: Extract project files archive and navigate to project directory. make clean make ./DSE performance Different components of the framework are invoked in the following order: DSE (project binary) → runprojectsuite.sh (shell script) → SimpleScalar DSE binary invokes runprojectsuite.sh script which in turn invokes SimpleScalar simulator with appropriate arguments. Several log files are generated in project directory on every invocation. 6. Anticipated Steps These steps can serve as a high-level guideline to aid you during the project: 1. Enter MY PSU ID in YOURCODEHERE.c. 2. Setup provided framework to get a set of results using the provided “unintelligent” heuristic. 3. Implement validateConfiguration and generateCacheLatencyParams functions. 4. Implement OurHeuristic in generateNextConfigurationProposal for both optimization goals (a well performing design and an energy efficient design) 5. Complete Report 7. Submission Requirements This is a group project. Submitted artifacts should include: 1. Project report 2. Code implementations of missing or stub functions within the provided framework 7.1. Project Report Your report must at conform to requirements listed in Appendix A. This report, data contained within and their analysis will be the primary means of assessing this project. Your report must be submitted via Canvas. (PDF only) 7.2. Code Implementations You will submit the source files (Makefile, runprojectsuite.sh, *.cpp and *.h) of your implementation as a single tar archive for an audit of your implementation efforts. Ensure that your code compiles on CSE machines without errors. You can make changes to framework if you conclude that they are required. The following commands will be used to compile and execute your code (followed by analysis of generated log files): # Extract project files archive and navigate to project directory. make ./DSE performance ./DSE energy 8. Modeling Considerations 8.1. Clock Cycle Time We will use the following very simplistic model for clock cycle time: The clock cycle time is determined by the fetch width, number of floating-point units, and whether the machine is in-order, or dynamic as follows: • Dynamic, fetch width = 1: 115 ps + FPU delay • In-order, fetch width = 1:100 ps + FPU delay • Dynamic, fetch width = 2: 125 ps + FPU delay • In-order, fetch width = 2: 120 ps + FPU delay • Dynamic, fetch width = 4: 150 ps + FPU delay • In-order, fetch width = 4: 140 ps + FPU delay • Dynamic, fetch width = 8: 175 ps + FPU delay • In-order, fetch width = 8: 165 ps + FPU delay FPU delay is determined by the number of floating-point units as follows: • count = 1: 5ps • count = 2: 10ps • count = 4: 20ps • count = 8: 40ps 8.2. Power & Energy 8.2.1. Core Leakage Power • Dynamic, fetch width = 1: 1.5 mW • In-order, fetch width = 1: 1 mW • Dynamic, fetch width = 2: 2 mW • In-order, fetch width = 2: 1.5 mW • Dynamic, fetch width = 4: 8 mW • In-order, fetch width = 4: 7 mW • Dynamic, fetch width = 8: 32 mW • In-order, fetch width = 8: 30 mW 8.2.2. Floating Point Unit Power • count = 1: 0.25 mW • count = 2: 0.50 mW • count = 4: 1 mW • count = 8: 2 mW 8.2.3. Cache and Memory Following list comprises tuples of format: [cache size or memory, access energy(pJ), leakage/refresh power(mW)] • 8KB: 20pJ, 0.125mW • 16KB: 28pJ, 0.25mW • 32KB: 40pJ, 0.5mW • 64KB: 56pJ, 1mW • 128KB: 80pJ, 2mW • 256KB: 112pJ, 4mW • 512KB: 160pJ, 8mW • 1024KB: 224pJ, 16mW • 2048KB: 360pJ, 32mW • Main Memory: 2nJ, 512mW 8.2.4. Energy per Committed Instruction • Dynamic, fetch width = 1: 10pJ • In-order, fetch width = 1: 8pJ • Dynamic, fetch width = 2: 12pJ • In-order, fetch width = 2: 10pJ • Dynamic, fetch width = 4: 18pJ • In-order, fetch width = 4: 14pJ • Dynamic, fetch width = 8: 27pJ • In-order, fetch width = 8: 20pJ 8.3. Validation Constraints You must implement these validation constraints in your code. Specifically, validateConfiguration and generateCacheLatencyParams must be implemented properly. 1. The il1 (L1 instruction cache) block size must be at least the ifq (instruction fetch queue) size (e.g., for the baseline machine the ifqsize is set to 1 word (8B) then the il1 block size should be at least 8B). The dl1 (L1 data cache) should have the same block size as your il1. 2. The ul2 (unified L2 cache) block size must be at least twice your il1 (and dl1) block size with a maximum block size of 128B. Your ul2 must be at least twice as large as il1+dl1 in order to be inclusive. 3. il1 size and dl1 size: Minimum = 2 KB; Maximum = 64 KB 4. ul2 size: Minimum = 32 KB; Maximum = 1 MB 5. The il1 sizes and il1 latencies are linked as follows (the same linkages hold for the dl1 size and dl1 latency): (a) il1 = 2 KB means il1lat = 1 (b) il1 = 4 KB means il1lat = 2 (c) il1 = 8 KB means il1lat = 3 (d) il1 = 16 KB means il1lat = 4 (e) il1 = 32 KB means il1lat = 5 (f) il1 = 64 KB means il1lat = 6 (g) The above are for direct mapped caches. For 2-way set associative add 1 additional cycle of latency to each of the above; for 4-way add 2 additional cycles; for 8-way add 3 additional cycles. 6. The ul2 sizes and ul2 latencies are linked as follows: (a) ul2 = 32 KB means ul2lat = 5 (b) ul2 = 64 KB means ul2lat = 6 (c) ul2 = 128 KB means ul2lat = 7 (d) ul2 = 256 KB means ul2lat = 8 (e) ul2 = 512 KB means ul2 lat = 9 (f) ul2 = 1024 KB (1 MB) means ul2lat = 10 (g) The above are for direct mapped caches. For 2-way set associative add 1 additional cycle of latency to each of the above; for 4-way add 2 additional cycles; for 8-way add 3 additional cycles; for 16-way add 4 additional cycles. 8.4. Miscellaneous Constraints These constraints have already been specified in the framework. Have a look at SimpleScalar invocation command in runprojectsuite.sh for an exhaustive list of specified parameters. Moreover, any parameter not specified in runprojectsuite.sh will default to SimpleScalar default settings. • mplat is fixed at 3 • fetch:speed is fixed at 1 • ifqsize can be set to a maximum of 8 words (64B) • decode:width and issue:width equal to your fetch:ifqsize • mem:width is fixed at 8B (memory bus width) • memport if fixed at 1 • mem:lat is fixed at 51 + 7 cycles for 8 word Appendices A. Project Report Minimum Requirements Your report must at least answer the following prompts in the exact same order. 1. Describe in 100 words or less how the provided framework and its components enable a design space exploration. 2. List the design point chosen by your DSE. 3. Fill out the following table as detailed below. 4. Plots as detailed below 5. Describe a more sophisticated heuristic which you expect will perform design space exploration (limited by 1000 design points) more effectively to find a better performing design (with respect to execution time). 6. Elaborate on any 2 new insights you gained while working on this project. 7. List of additional resources used (optional) 8. Additional information or comments (optional) A.1. Table In each cell specify the parameter value followed by why this value guided the DSE closer to your optimization goal (for example: more ALUs allow extraction of more ILP and increase performance). Make sure the parameters are in the exact order as they appear in runprojectsuite.sh Parameter Performance EDP Param1 (i.e. width) Value = Value = Why = Why = Param2 (i.e. scheduling) Value = Value = Why = Why = … … ParamN Value = Value = Why = Why = A.2. Plots The report should include the following four plots: A. Line plot of normalized geomean execution time (y axis) for each considered design point vs. number of designs considered (x axis) B. Line plot of normalized geomean of energy-delay product (y axis) vs number of designs considered C. Bar chart showing normalized per-benchmark execution time and geomean normalized execution time for the best performing design D. Bar chart showing per-benchmark normalized energy-delay product and geomean normalized energy delay product for the most energy-efficient design found These four plots must be labelled in your report corresponding exactly to numbering in the list above. Furthermore, axis in the plots should be properly labelled. A.3. Other Guidelines For clarity in the written report, when listing the best design points, please do not represent them in terms of their index representations (e.g. 1 0 0 5 2 …) and instead describe the actual value used for each dimension in a table or similar presentation. B. Project FAQs Q: What are the column headers for the .log file? A: normalized EDP, normalized Execution time, absolute EDP, absolute Execution time. The writes to both the .best and .log files are generated near the end of main. Q: What are the column headers for the .best file? A: Headers differ by line: Line 1 headers: bestEDPconfig, normalized EDP of bestEDPconfig, normalized Execution time of bestEDPconfig, absolute EDP of bestEDPconfig, absolute Execution time of bestEDPconfig, absolute EDP of Bench 0 on bestEDPconfig, normalized EDP of Bench 0 on bestEDPconfig, absolute EDP of Bench 1 on bestEDPconfig, normalized EDP of Bench 1 on bestEDPconfig, absolute EDP of Bench 2 on bestEDPconfig, normalized EDP of Bench 2 on bestEDPconfig, absolute EDP of Bench 3 on bestEDPconfig, normalized EDP of Bench 3 on bestEDPconfig, absolute EDP of Bench 4 on bestEDPconfig, normalized EDP of Bench 4 on bestEDPconfig Line 2 headers: bestTimeconfig, normalized EDP of bestTimeconfig, normalized Execution time of bestTimeconfig, absolute EDP of bestTimeconfig, absolute Execution time of bestTimeconfig, absolute Time of Bench 0 on bestTimeconfig, normalized Time of Bench 0 on bestTimeconfig, absolute Time of Bench 1 on bestTimeconfig, normalized Time of Bench 1 on bestTimeconfig, absolute Time of Bench 2 on bestTimeconfig, normalized Time of Bench 2 on bestTimeconfig, absolute Time of Bench 3 on bestTimeconfig, normalized Time of Bench 3 on bestTimeconfig, absolute Time of Bench 4 on bestTimeconfig, normalized Time of Bench 4 on bestTimeconfig Q: Why are there only 18 configuration parameters when SimpleScalar (and the project specification) list so many more? A: There are 18 configuration variables, and more derived settings from those 18 configuration variables, and still more settings that are fixed as constant (e.g. MPLAT). Given the block size (set independently), associativity (set independently), and number of sets (set independently), you can determine total cache size for the L1D and I caches and then validate if the latency for that cache (set independently) is set correctly. Q: What’s a quota error, why are half my output files empty, and why can’t I make new files anymore? A: It means you are out of disk space. Each run of this program produces a large number of intermediate output files for the evaluated design points. These are kept to speed up subsequent evaluations of the same design point in future runs as a means of reducing debugging/heuristic development time. Consider cleaning out your browser caches if you are low on disk quota before performing a project run.
Table of ContentsAssignment Overview 3Learning Objectives 3Advice 3Getting Started 4Codio Setup 4Starter Code 4my_string.h 4my_string.c 4program1.c 4Background – Introduction and my_strlen 5Problem 1 – Creating Your Own Library of String Functions 6Overview 6Requirements 6Hints 7Problem 2 – Adding Non-Standard String Functions to Your Library 8Overview 8Requirements 9Problem 3 – Parsing Strings 11Overview 11The sscan and sprintf functions 11Arguments to main 11Problem 3 Task 12Requirements 12Problem 4 (Extra Credit) – my_strtok 14Overview 14Requirements 14A Hint 14Testing Your Functions 15Submission 16Submission Checks 16Consistency Checks 16The Actual Submission 16Grading 17Main Assignment 17Extra Credit 17Important Notes on Plagiarism 18Hints or FAQs 18Resources 19 In lecture you have learned that in C an array of characters with a NULL termination is considered a String, whereas an array of characters without a NULL termination is simply an array of characters. The standard library is available with most C compilers that includes several functions designed to work with and manipulate Strings in C. Strings are so common in C that knowing how to use these functions in C is considered a basic skill.The goal of this assignment is to give you experience with strings in C and with the library of functions designed to work with strings, give you an appreciation of how those functions work, and also continue to help you work with pointers and arrays (in the context of C Strings). We have provided a basic framework and several function definitions that you must implement.This file contains the function declarations you must implement. Aside from adding the required declarations for my_strrev, my_strccase, and optionally my_strtok, do not modify this file. This file contains empty implementations for the functions defined in my_string.h. We have provided the implementations of my_strlen using array notation and pointer arithmetic for you. You will provide the remaining implementations in this file. This is a test environment program only. We will not review it or even look at it and it will not be used for grading. You are free to write any code necessary to test your implementations. In lecture, we discussed a commonly used function, strlen, that is part of the string.h library. Its job is to take in a C String, count the number of characters up to (but not including) the NULL character and return the string’s length. As an example, if our string waschar my_string [100] = “Tom” ;strlen(my_string) would return 3.Even though there are 100 bytes allocated on the stack for the string, since there are only 3 characters (followed by a NULL), the length of the string is indeed 3.In lecture, we presented two versions of a strlen-like function. One function uses array notation and the other uses pointer notation. Ultimately they perform the same operation.my_strlen_array treats the incoming argument (char* string) as if it is an array using array notation (i.e. with square brackets [ and ])size_t my_strlen_array(const char *str)int len = 0 ;while (str[len] != ‘’) {len++ ;}return (len) ;} my_strlen_pointer treats the incoming argument as the pointer it truly is, using pointer arithmetic to determine the string’s length.size_t my_strlen_pointer(const char *str)const char* s;for (s = str; *s; ++s) ;return (s – str);}Note: size_t is not an actual C type; is a “typedef’ed”, that is, it is a shortcut for unsigned long. Your task for this assignment is to implement your own library of string functions to mimic the standard C library string functions.In Codio, we have provided a header file called my_string.h. In that header file, we have declared several functions: my_strlen_array, my_strcpy_pointer, etc.In my_string.c, we have implemented only two of the many functions: my_strlen_array and my_strlen_pointer, as described above. You will implement the remaining functions.In a third file: program1.c, we have provided some basic code that calls the functions in your my_string library and compares the output of them to functions in the standard C-library string.h. This is one way to quickly check if your output is correct. Look carefully at these three files before continuing. For this problem, your task is to implement your own library of string functions to mimic the standard C library string functions. int main (int argc, char** argv) ;int main (int argc, char** argv) {printf (“# of arguments passed: %d ”, argc) ;for (int i=0; i< argc ; i++) {printf ( “argv[%d] = %s ”, i, argv[i] ) ;}return (0) ;}./program3 arg1 2 arg3 4 arg5 There is a single “submission check” test that runs once you upload your code to Gradescope. This test checks that you have submitted all required files and also that your program compiles and any autograder code compiles successfully. It does not run your program or provide any input on whether it works or not. This check just ensures that all the required components exist. This test is performed after uploading to Gradescope.Ensure that you are passing this check before closing Gradescope. If you are not passing this check, please reach out to TAs for troubleshooting assistance.The autograder will also show the results of six tests:The remaining tests will be hidden until after grades are published. You will submit this assignment to Gradescope in the assignment entitled Assignment 10: Strings in C.Download the required .c source and .h header files (as well as any additional helper files required) and your Makefile from Codio to your computer, then Upload all of these files to the Gradescope assignment. We expect my_string.c, my_string.h, program3.c, and makefile. Do not submit program1.c, program2.c., or program4.c.Do not not submit intermediate files (anything .o).You have unlimited submissions until the deadline, after which late penalties apply as noted in the syllabus.We will only grade the last submission uploaded.Do not mark your Codio workspace complete. Only the submission in Gradescope will be used for grading purposes.There is no page matching and no academic integrity submission for autograder assignments. This assignment is worth 127.5 points, normalized to 100% for gradebook purposes.Problem 1 (standard functions) is worth 72 points (each function is 9 points, with equally weighted sub-tests per function).Problem 2 (custom functions) is worth 18 points (each function is 9 points, with equally weighted sub-tests per function).Problem 3 (parsing strings) is worth 10 points. Problems 1, 2, and the Extra Credit are tested with Unit Testing. We will run different scenarios for each function to validate the functionality (partial credit based on which tests fail).Problem 3 checks the final output produced by your program and compares that output to the expected output. It must match exactly for credit: double check that your program does not have any extra output.We will only grade the last submission, regardless of the results of any previous submission.We will not be providing partial credit for autograder tests.You may ask for feedback by submitting a regrade request using the Miscellaneous Adjustments rubric item. The Extra Credit is worth 6 percentage points so the highest grade on the assignment is 106%.Your extra credit must not break functionality for the non-extra credit requirements.There is no partial credit. It must work completely for any credit.We will not give guidance on how to do this since it is designed to be challenge problem. Hints from previous semesters strlen referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strlen.htm strcpy referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strcpy.htm strchr referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strchr.htm strcat referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strcat.htm strcmp referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strcmp.htm sscanf referencehttps://www.tutorialspoint.com/c_standard_library/c_function_sscanf.htm sprintf referencehttps://www.tutorialspoint.com/c_standard_library/c_function_sprintf.htm strtok referencehttps://www.tutorialspoint.com/c_standard_library/c_function_strtok.htm strtok reference (Linux manual pages)https://man7.org/linux/man-pages/man3/strtok_r.3.html The const modifierhttp://www.geeksforgeeks.org/const-qualifier-in-c/
Hello Indiana Drones! We unconvered the location of an invaluable piece of ancient treasure – the likes of which we have never seen before. Unfortunately, the treasure is located in a dense and dangerous jungle making a typical safari impossible. That’s where you come in! As a drone navigation and extraction expert, your mission should you choose to accept it, is to : Part A SLAM (worth 60 points) : Estimate The Locations Of Trees In The Jungle Environment And The Drone Given Pre-Scripted Movements and Measurements Complete the SLAM class in the indiana_drones.py file. To test your SLAM module, testing_suite_indiana_drones.py initiates a drone at (0,0) in a jungle with a lot of trees for each test case. The location, size and number of the trees are intially unknown to you. The drone moves through the jungle environment in a series of pre-scripted movements. At each time step, the drone’s sensors report measurements that are passed through your process_measurements function and the makes movements that are passed through your process_movement function. The goal of these functions is to update your belief of the locations of the drone and trees in your environment given the measurement and movement inputs. Those estimates will be read using your get_coordinates function and compared against the ground truth. The drone’s sensors report the distance (m), bearing (rad) and size (m) of trees (within the sensor’s horizon) relative to the drone’s location and orientation (See Figure 1 – Measurement). Note : since you only see trees within the sensor’s horizon, trees may appear and disappear in your measurements as you move through the environment and get closer/further to previously unseen/seen trees. The drone’s controller turns the drone by the pre-scripted steering angle (rad) followed by a movement in a straight line by the pre-scripted distance (m) (See Figure 1 – Movement). Both the measurement and movement have gaussian noise in their distance and bearing/steering. In each test case, 30 points is for accurately estimating (within a 0.25 meter radius) the position of your drone and 30 points is for accurately estimating (within a 0.25 meter radius) the location of each of the trees. Points are deducted for each inaccuracy. Figure 1: Drone Diagram Part B Navigation (worth 40 points) : Navigate To The Treasure While Avoiding Trees In Your Path and Extract It Complete the IndianaDronesPlanner class in the indiana_drones.py file To test your SLAM module, the testing_suite_indiana_drones.py initiates a drone at (0,0) in a jungle with a lot of trees for each test case. The location, size and number of the trees are initially unknown to you. There is a piece of treasure in the environment whose location is known to you. The goal of your planner should be to move towards the treasure and extract it while avoiding crashes with trees on its way. At each time step, the drone’s sensors report their measurements and this is provided as input to the next_move function along with the location of the drone. The output of the function is used to move the drone through the jungle environment/extract the treasure. The output of your navigation algorithm can be one of two actions in the next_move function: namely move and extract. The move action moves the drone by the steering angle and distance you prescribe. Your drone has a maximum turning angle [in radians] and a maximum distance [in meters] that it can move each timestep [both passed using a parameter]. Movement commands that exceed these values will be ignored and cause the drone to not move. The extract action extracts the treasure at your location. The treasure will only be extracted if it is within the defined radius (0.25 meters). If not there will be a time penalty for extracting dirt. You should specify the movement as follows: move 1 1.57. [command distance steering] which means the drone will turn counterclock-wise 90 degrees [1.57 radians] first and then move a distance of 1 meter. When you issue your extract action you should supply 3 arguments total, including the treasure type (*) and current estimated location (x, y) of the drone as follows: extract * 1.5 -2.1 [command treasure_type x y]. Whenever the drone enters within a particular radius of a tree’s center (i.e. the canopy of a tree), it is deemed to have crashed. In this project we assume the drone is a point (even though in the visualization it occupies some area). Note : The drone moves on a straight line path, so even if the starting and ending points of your movement aren’t inside the tree’s canopy, the path could still intersect the tree, which would result in a penalty. The line_circle_intersect function in testing_suite_indiana_drones.py may be helpful. 40 points is for extracting the treasure within the time limit, of which 10 points is deducted for each tree crash (upto a maximum of 20 points). For example, if the drone extracted the treasure within the time limit but crashed into one tree and one tree only, you will receive 30 points. We are using the Gradescope autograder system which allows you to upload and grade your assignment with a remote / online autograder. You must submit your indiana_drones.py file (only) to Gradescope to receive credit. Do not archive (zip,tar,etc) it. Your code must be valid python code, and you may use external modules. We encourage you to keep any testing code in a separate file that you do not submit. Your code should also NOT display a GUI or Visualization when we import or call your function under test. We have provided a testing suite and test cases similar to the one we’ll be using for grading the project, which you can use to help ensure your code is working correctly. These testing suites are NOT complete, and you will need to develop other, more complicated, test cases to fully validate your code. We also recommend making your own simple/trivial test cases to unit test your algorithm as you code it. We encourage you to share your test cases (only) with other students on Ed Discussions. The testing_suite_indiana_drones.py will run all cases from both part A and part B 10 times, remove the lowest score for each and average the rest to calculate your score. It will do this automatically (i.e. you do not need to loop your code). Since the score is stochastic and may have small variations, feel free to run your code on Gradescope multiple times. Ensure that your code consistently succeeds on each of the given test cases as well as on a wide range of other test cases of your own design. For each test case, your code must complete execution within the prescribed time limit (10 seconds) or it will receive no credit. Note that the grading machine is relatively low powered, so you may want to set your local time limit to 5 seconds to ensure that you don’t go past the CPU limit. Note that if VERBOSE is on in the testing_suite_indiana_drones.py file, printing will take a lot of time and slow down your execution. So please feel free to increase the time limit while debugging with the VERBOSE on, but when you submit your code, it should run within the 10 second time limit on Gradescope. Usage: python testing_suite_indiana_drones.py A visualization file has been provided to aid in debugging. The visualization will plot 6 pieces of data: the real location of drone, the estimated location of drone, the real location of trees, the estimated location of trees, the types of the trees (‘A’, ‘B’, …etc) and the location of treasure present in the environment. The real location of the drone will be a drone with 4 rotors. The estimated location of the drone will be a small blue dot. The real location of trees will be represented by circles of varying radii. The trees that are visible to the drone’s sensors are green in color and the trees that are too far away for the sensor to detect are in gray. The estimated location of a tree will be a small black dot. The type of tree/treasure will be next to the real location. The treasure is represented by a red triangle. The estimated points to plot need to be returned from next_move as a 2nd (optional) value in the form of a dictionary. This is needed to show your SLAM system’s estimates of drone and landmark location in the visualization. The keys should be the landmark id and the values should be its x,y coordinates. The key representing the drone’s estimated location will be ‘self’. {‘self’: (.2, 1.5), landmark id 1: (.4,1.9)} Usage: python visualize.py [-h] [–part {A,B}] [–case {1,2,3,4,5}] Example to run the visualization: python visualize.py –part B –case 3 The visualize.py and testing_suite_indiana_drones.py have a VERBOSE FLAG. If the FLAG is True, it will print helpful outputs in the terminal for debugging. In addition, there is a NOISE_FLAG in the testing_suite_indiana_drones.py. Ensure that your code works with no noise first before you test against a noisy environment. Q: I’m confused. We are given so many files. What exactly should we do again and in which file? A: The main file you are concerned with is indiana_drones.py. This is what you fill and submit to gradescope. It contains two classes (SLAM and IndianaDronesPlanner) whose methods are used by the testing_suite_indiana_drone.py to run SLAM and Navigation respectively in various test cases to generate your score. drone.py contains helper classes and methods that you are free to use in your implementation. visualize.py is provided to help you debug your code with a visualization. Q: Where does the drone start? Which way is it facing? A: Although the drone starts in different places in different test cases, you can assume that it starts at (0,0) for each test case and report your outputs accordinly. Your drone will always have a bearing of zero degrees when it starts (i.e. facing east). Q: What are the (x,y) return values from get_coordinates function relative to? A: They should return your best guess for the position of the drone and trees relative to the drone’s starting location (0,0). Q: How can I uniquely identify trees in the environment? A: Each tree will have a unique landmark id. Although there may be more than one of the same type of tree in the area, each will have a unique id.
Network science and Graph Learning Credits: Some of these problems have been adapted from the following classes: • Prof. Aaron Clauset Network Analysis and Modeling, 2014 Submitting answers: Prepare answers to your homework in a single PDF/DOCX file and submit it via Moodle. Submitting code: Provide a link to a github classroom repository containing all code assignment. Failure to submit your code will result in reduction of all points for that question from your project score. Background Information Facebook100 is a dataset of Facebook friendship connections from each of the 100 US universities during a single-time snapshot in fall 2005 (when one had to have a .edu account to be on Facebook). The dataset is avalaible inside the following github repository https://classroom.github.com/a/jm4seIEs or you can download the dataset from the following link: https://partage.imt.fr/index.php/s/iyFWSQPJNmc7AC7 Facebook history (this text is extracted from the sec. 2 of [1]) Harvard Friendster launches Columbia Stanford Yale Cornell, Dartmouth UPenn, MIT LinkedIn launchesNYU, BU Duke, Georgetown, UVA BC, Tufts, Northeastern, Illinois Florida, Wellesley, Michigan, Michigan State, Northwestern UCLA Thefacebook.com Emory, UNC, Tulane, UChicago, Rice launches at HarvardWashU UC Davis, UC San Diego USC Caltech, UC Santa Barbara Rochester, Bucknell Williams, Amherst, Swarthmore, Facebook drops the “the” Wesleyan, Oberlin, Middlebury,Hamilton, Bowdoin South Florida, Central Florida, Florida State, GWU, Johns Hopkins Syracuse, Notre Dame, Maryland Maine, Smith, UC Irvine, Villanova, Virginia Tech, UC Riverside, Cal Poly, Mississippi, Michigan Tech, UCSC, Indiana, Vermont, Auburn, U San Fran, Facebook launches News Feed William & Mary, Miami, James Madison, UT Austin,Wake Forest, Santa Clara, American, Haverford, Facebook open to everyone Simmons, Binghamton, Temple, Texas A&M, Vassar, Pepperdine, Wisconsin, Colgate, Rutgers, Howard, UConn, UMass, Baylor, Penn State, Tennessee, Lehigh, Oklahoma, Reed, Brandeis Trinity (and 9 others) (a) Key milestone in the early history of Facebook (Figure extracted from [1] (b) Fraction of undergraduate that adopted Facebook vs. network index Figure 1 Description of the network dataset For nearly all colleges, alumni made up about 10-25% of users, a number that increased with the age of the network. Vertices labeled as faculty, staff or students who were not regular undergraduates (graduate students and summer students) made up on average 4.1% of each population. Question 1: Reading Read the following documents [3, 2, 1] Question 2: Social Network Analysis with the Facebook100 Dataset The smallest network (Caltech) has 762 nodes in the largest connected component (LCC), and the largest has more than 40000 nodes in the LCC. Lets use three networks from the FB100: Caltech (with 762 nodes in the LCC), MIT (which has 6402 nodes in the LCC), and Johns Hopkins (which has 5157 nodes in the LCC). (a) (1 point) For these three networks plot the degree distribution for each of the three networks that you downloaded. What are you able to conclude from these degree distributions? (b) (1 point) Compute the global clustering coefficient and mean local clustering coefficient for each of the 3 networks. In addition compute the edge density of each network. Should either of these networks be construed as sparse? Based on the density information and the clustering information what can you said about the graph topology? (c) (1 point) For each network, also draw a scatter plot of the degree versus local clustering coefficient. Based on these calculations as well as your previous ones, are you able to draw any conclusions about any similarities or differences between the tree networks? What other observations can you make? Question 3: Assortativity Analysis with the Facebook100 Dataset In this question we expect you will compute the assortativity on a large set of graphs (if possible all the graphs). (a) (2 points) Of the FB100 networks, investigate the assortativity patterns for five vertex attributes: (i) student/faculty status, (ii) major, (iii) vertex degree, and (iiii) dorm, (iiiii) gender. Treat these networks as simple graphs in your analysis. For each vertex attribute, make a scatter plot showing the assortativity versus network size n, with log-linear axes for all 100 networks, and a histogram or density plot showing the distribution of assortativity values. In both figures, include a line indicating no assortativity. Briefly discuss the degree to which vertices do or do not exhibit assortative mixing on each attribute, and speculate about what kind of processes or tendencies in the formation of Facebook friendships might produce this kind of pattern. For example, below are figures for assortativity by gender on these networks. The distribution of points spans the line of no assortativity, with some values nearly as far below 0 as others are above 0. However, the gender attributes do appear to be slightly assortative in these social networks: although all values are within 6% in either direction of 0, the mean assortativity is 0.02, which is slightly above 0. This suggests a slight amount of homophily by gender (like links with like) in the way people friend each other on Facebook, although the tendency is very weak. In some schools, we see a slight tendency for heterophily (like links with dislike), as one might expect if the networks reflected heteronormative dating relationships.Network size Gender Assortativity Figure 2: a) Gender assortativity as function of the networks size. b) Gender assortativity distribution. Question 4: Link prediction In this question we expect you will compute the link prediction algorithms on a large set of graphs (> 10). (a) Read the following documents [4]. (b) (2 points) Implement the following link prediction metrics: common neighbors, jaccard, Adamic/Adar. We use the scikit-learn API as an example for our implementation of the link prediction metrics. Please use the implementation (in listing. 1) as an example. Your implementation should inherit from the class LinkPrediction defined in listing. 1. You should implement yourself the given metrics, don’t used the ones defined in Networkx (c) (2 points) Evaluating a link predictor: 1. Select graph Gfb(V,E) in the Facebook100 dataset 2. randomly remove a given fraction f ∈ [0.05,0.1,0.15,0.2] of edges Eremoved from the original graph Gfb. 3. For each node pair in the graph |V |×|V |, for each node pair compute the link predictor metrics of interest p, these are the predicted ”friendship” Epredict. 4. Sort in decreasing order of confidence as a function p from the node pair Epredict and then we take the first k pairs of nodes . 5. Compute the size of the intersection between the edge set of removed edges and the edge set of predicted node . Then compute the top@k, recall@k and precision@k (for k = 50,100,200,··· ,400) using the k best scored edges provided by link predictor algorithm (see [5] for more information). Where the top@k predictive rate is the percentage of correctly classified positive samples among the top k instances in the ranking produced by a link predictor P.Prediction Terminology: TP stands for true positives, TN stands for true negatives, FP stands for false positives, and FN stands for false negatives. (d) (2 points) Choose a couple of graphs in the facebook100 dataset run and evaluate each link predictor on them, and conclude on the efficiency of the following metrics: common neighbors, jaccard, Adamic/Adar. from abc import ABC from abc import abstractmethod import networkx as nx import numpy as np import progressbar class LinkPrediction(ABC): def __init__(self, graph): “”” Constructor Parameters ———graph: Networkx graph “”” self.graph = graph self.N = len(graph) def neighbors(self, v): “”” Return the neighbors list of a node Parameters ———v: int node id Return —–neighbors_list: python list “”” neighbors_list = self.graph.neighbors(v) return list(neighbors_list) @abstractmethod def fit(self): raise NotImplementedError(“Fit must be implemented”) class CommonNeighbors(LinkPrediction): def __init__(self, graph): super(CommonNeighbors, self).__init__(graph) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 Listing 1: Python implementation example of a Link prediction metric Question 5: Find missing labels with the label propagation algorithms In this question we expect you will compute the label propagation algorithm on a large set of graphs (> 10). We studied in class two algorithms with the name ”label propagation” that have different objective, choose wisely the one to implement. (a) Read the following document [6]. (b) (2 points) Implement in python the label propagation algorithm [6], please consider pytorch and networkx for the development of your algorithm. (c) (2 points) Choose a network from The Facebook100 dataset and randomly select 10%, 20%, and 30% of of the node attributes of the network to be removed. Use the label propagation algorithm you implemented to recover the missing attributes. Perform this operation for each of the following attributes : ”dorm”, ”major”, ”gender”. fraction removed 0.1 0.2 0.3 0.4 Duke Major 0.282 0.265 0.255 0.241 Dorm 0.529 0.523 0.500 0.463 Y ear 0.913 0.905 0.898 0.891 Gender 0.675 0.684 0.682 0.679 Table 1: Accuracy of the label propagation algorithm ) (1) (e) (1 point) Conclude on the accuracy of the label propagation algorithm for different labels, could you explain why is there such difference in the accuracy between each type of label ? Question 6: Communities detection with the FB100 datasets Formulate a research question about group formation among students in the FB100 dataset. To validate your hypothesis, use only a few universities and a community detection algorithm of your choice to extract the different groups of students. To help you formulate a research question, some of the following references might be useful [8, 9] and section 3.4 in [2]. (a) (1 point) Formulate a research question about group formation in FB100 and explain your hypothesis. (b) (1 point) Write the code to validate your research question and show the result using a few selected community detection algorithms and graphs. (c) (1 point) Explain the results and conclude whether your experiment confirms your initial hypothesis. References [1] Jacobs, A. Z., Way, S. F., Ugander, J. & Clauset, A. Assembling thefacebook: Using heterogeneity to understand online social network assembly. In Proceedings of the ACM Web Science Conference, WebSci ’15, 18:1–18:10 (2015). URL https://arxiv. org/abs/1503.06772. [2] Traud, A. L., Kelsic, E. D., Mucha, P. J. & Porter, M. A. Comparing community structure to characteristics in online collegiate social networks. SIAM Review 53, 526–543 (2011). URL https://arxiv.org/abs/0809.0690. [3] Traud, A. L., Mucha, P. J. & Porter, M. A. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications 391, 4165 – 4180 (2012). URL https://arxiv.org/abs/1102.2166. [4] Liben-Nowell, D. & Kleinberg, J. The link prediction problem for social networks. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03, 556–559 (2003). URL https://www.cs.cornell. edu/home/kleinber/link-pred.pdf. [5] Yang, Y., Lichtenwalter, R. N. & Chawla, N. V. Evaluating link prediction methods. Knowledge and Information Systems 45, 751782 (2014). URL http://dx.doi.org/ 10.1007/s10115-014-0789-0. [6] Bhagat, S., Cormode, G. & Muthukrishnan, S. Node Classification in Social Networks. In Social Network Data Analytics, 115–148 (Springer US, 2011). URL https:// arxiv.org/abs/1101.3291v1.
INFO2222 Project: Usability Part1 Usability Project DescriptionYou already have an account and messaging service that allows pair-wise communication among students and to specific academic/administrative staff who they add as friends. New additional requirements are as below:Basic Functionality Requirements:a. Improved design for usability and user experience b. Friends should display whether they are online or not in the friends list, along with their account role (student, staff, etc). c. Friends should be able to be removed d. Users can receive messages from friends even when the recipient is not currently in a chatroom. They will be stored in the message history database and loaded when the other user connects to the chatroom.a. Staff and students can make and modify articles b. Staff can delete articles or modify articles made by others c. Students and staff can comment on articles d. Staff can delete comments e. Staff can mute / unmute users to prevent them from posting or joining a chatroom.Additional Criteria:a) Paper or digital wireframe drawings b) Prioritised list of features and design considerations based on guerilla testinga) User acceptance testing, results and findings of the tests over at least 2 iterations b) Final evaluation and list of features or extensions planned for the future.2 Recommended ActivitiesStep 1: User Investigation. During this phase, you are to investigate a chosen user group to determine what they need from your website. To make things easier, you can concern yourself with only a single type of user: • Students – this can range from any students starting just starting their program of studies to final year students. It can also include students transferring into a computing program from other USyd schools; OR • Alumni – graduates who are willing to give back to their alma mater and to guide their juniors; OR • SCS/administrative staff – this can include program managers, academic advisors and adminis- trative staff responsible for the running of program operations that affects students’ academic performance.Perform a PACT analysis for your chosen group. You will likely still find that your selected group is too large and complex but your analysis should help you identify what you know about your target group and what you need to find out during your investigation to narrow your group down to a single persona.Expected outputs: • Outline of the user investigation process (surveys/interviews, how many?) that your group has used to narrow down your target user. • Research materials used to collect data about your target group • A persona document outlining your target persona • Based on your findings above, gather content (collection of documents or articles) relevant to the interests of your target persona. Ensure you cite all sources and quote where you have copied text verbatim. This content will be used in the example posts made to showcase your knowledgebase’s functionality.Step 2: Navigation design. Your design plan will need to include the user actions stated in the core requirements in addition to actions discovered specifically for your own target user group (user specific functions). Conduct a card sorting session with some of your target user group and use your results to create the navigation map (site map) of your website.Expected outputs: • Outline of card sorting session along with all materials that were used. • Information architecture of your websiteStep 3: Design-Evaluate – Low Fidelity or High Fidelity Prototype (paper or digital): Based on the information architecture that you have from the previous phase, brainstorm and create sketches of your website. Create a prototype of the best design and perform a guerrilla test with target users using this prototype. Each of your team members should take part in the guerrilla test, and there should be at least one participant outside of your team.Expected outputs: • A prioritized list of features – these do not need to all be developed in the actual web application, but are more like a ‘wish list’ of things that would enhance the usability and user experience. It is expected that there would not be enough time to actually develop all of them in this assignment project. • Outline steps taken to determine the ‘best’ design to be developed • Paper or digital prototype – wireframe diagrams • Mini-report that outlines how the guerrilla test was conducted, raw results, materials used and findings of the test.Step 4: Design-Evaluate (Initial Implementation of Prototype) Focus on converting your (improved) prototype (paper or digital) to the real web server. Do this incrementally and perform evaluations (e.g., think aloud test) to ensure that you are on the right track.It is recommended that you create a github repository (you can use https://github.sydney.edu.au/) toExpected outputs: o Which features were completed in the first iteration? What was the result of the user testing after the first iteration? Which features were prioritised for the second iteration? • Outline of evaluations conducted • Demonstration of the functionalities mentioned at the beginning: admin roles, the user specific function etc. • Any thoughts and self-evaluation about how the team worked together and each member’s contribution to the development process.Your output in Step 4 does not need to be perfect, we care more about your improvements over each iteration and the evaluations conducted to improve usability.Step 5: Final report • It is a collection of all the previous outputs in a neat format. • Your final submission should consist of two files: a pdf file containing the report and a zip file containing your code and other artifacts.3 Demonstration4 Group Member Contribution AdjustmentGroup Mark = X points based on criteria Bonus Mark = (Actual Contribution/50 – 1) * 20% Penalty = (Actual Contribution/50 – 1) * 100% Penalty Reduction = ((50 – Reported Contribution) / (50 – Actual Contribution)) * 25%If Bonus Mark > 0: Student receives X * (1 + Bonus Mark) Else If Penalty > 0: Student receives X * (1 – Penalty * (Penalty Reduction)) Else: Student receives XFor example:• If Student A and Student B both contribute 50% each, then there is no adjustment and they both receive the same mark X/100. o If Student B reported their contribution honestly (25% or less) then they receive a reduction in their penalty of up to 25% – so instead of -50%, they would get -37.5%. o If Student B reported their contribution dishonestly (50% or more) then they would receive the full -50% penalty. o If Student B reported their contribution less than 50% but greater than 25%, then they would receive a reduction in their penalty linearly scaled in this range – so if they reported 40%, then they get (10/25)*25% = 10% reduction in their penalty, so they receive -45% penalty instead of -50%. • If Student A contributed 100% and Student B contributed 0%, then Student A receives +20% bonus, and Student B receives -100%. • If Student A contributed 80% and Student B contributed 20%, then Student A receives +12% bonus and Student B receives -60%. • If Student A contributed 55% and Student B contributed 45%, then student A receives +2% bonus mark and Student B receives -10% penalty (if student B reported their contribution as 45% or less, they only receive -7.5% penalty).The actual contribution percentage will be determined based on a range of factors including: • The demonstration during class • Responses to confidential progressive weekly surveys and final survey (reported contribution) • Division of tasks explained in the group report • Additional evidence provided by group members
INFA723 Homework 4 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L.1. (60 points) Tcpcrypt is a TCP extension designed to make end-to-end encryption of TCP traffic the default, not the exception. To facilitate adoption tcpcrypt provides backwards compatibility with legacy TCP stacks and middle boxes. The paper, “The case for ubiquitous transport-level encryption”, is available for you to go through all the details. You can also go to http://tcpcrypt.org/ and find more information about Tcpcrypt. Read the paper and answer the following questions: a. (20 points) Tcpcrypt is a transport layer security protocol. As we discussed in the class, TLS is also a transport layer security protocol. Compare the differences between Tcpcrypt and TLS protocol (list at list three differences) b. (20 points) What is the design consideration of Tcpcrypt protocol? Why is it necessary? c. (20 points) Tcpcrypt was originally proposed in 2010. What are the major challenges to adopt Tcpcrypt?2. (15 points) Figure 1 shows a diagram of how to retrieve public keys using a public key authority. In steps 3, 6, and 7, two nonce N1, N2 are used. Explain why N1, N2 are used in the protocol and what security service can be ensured by using N1, and N2 in the protocol. (Hints: think about non-repudiation service in OSI model)Figure 1 Retrieve Public Keys using a Public-key Authority3. (15 points) Users A and B uses the Diffie-Hellman key exchange technique with a common prime q = 71 and a primitive root α = 7. a. (5 points) If user A has private key XA = 5, what is A’s public key YA ? b. (5 points) If user B has private key XB = 12, what is B’s public key YB ? c. (5 points) What is the shared secret key? (Hints: refer to text book Figure 10.1 in Page 303) 4. (10 pints) Consider a one-way authentication technique based on asymmetric encryption: 1. A->B: IDA 2. B->A: E(PUa , R2) 3. A->B: R2 a) Explain the protocol; b) What type of attack is this protocol susceptible to?
INFA723 Homework 2 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. Note: For all the programming assignments, you can choose any operating systems to develop your code. A README.txt is required to submit any programming assignments. In the README.txt, you need to provide the following information: 1) How to compile your program? 2) How to run your program? 3) What is the output and the results when I run your program? 4) Any descriptions which can help me understand, compile, run, and verify your answers. (FYI: I check every programming assignment turned in!) Zip all you source code, project files, supporting files, and README.txt and submit the all-in-one zip file together to the D2L Dropbox. (50 points) 1. Three binary files are provided in this exercise, q1-file1, q2-file2, and q3-file3. There three files include a firmware image, an encrypted file, and a compressed file. a) (20 points) Write a program to classify if a file is encrypted or not. b) (10 points) Explain what you use in the code to determine if a file is encrypted. c) (10 points) Identify each file’s category including firmware image, encrypted file, and compressed file. d) (10 points) If you can identify the compressed file, are you able to identify which algorithm is used to compress the file and un-compress the file. (50 points) 2. Cipher.txt is an encrypted file. The cipher.txt is created using AES algorithm. The key size is 192. The mode of operations is CBC. The key and initial vector are listed as below: key=0294E7143C2DF135DAEFE9D74DF8BDCC488EDBA8FE5239A8 iv =F3BC6E5B281EBF67210CD68837FFDE9A a) Write a program to decrypt the cipher.txt. b) Submit a copy of the plaintext you decrypt.
INFA723 Homework 3 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. Note: For all the programming assignments, you can choose any operating systems to develop your code. A README.txt is required to submit any programming assignments. In the README.txt, you need to provide the following information: 1) How to compile your program? 2) How to run your program? 3) What is the output and the results when I run your program? 4) Any descriptions which can help me understand, compile, run, and verify your answers. (FYI: I check every programming assignment turned in!) Zip all you source code, project files, supporting files, and README.txt and submit the all-in-one zip file together to the D2L Dropbox. (50 points) 1. A self-signed certificate (cert.cer) and its corresponding private key (prikey.pem) are provided in this question. The certificate includes information such as the certificate version number, the signature hash algorithm, the public key algorithm, the public key, etc. Answer the following questions: a) What is the signature hash algorithm used to create the certificate? b) What is the public key algorithm used in the certificate? c) What is the public key size? d) trackbcipher.txt is a cipher file encrypted using the certificate. The command line used to encrypt the plaintext file trackb.txt is shown below: > openssl smime -encrypt -binary -aes-256-cbc -in trackb.txt -out trackbcipher.txt -outform DER cert.cer Decrypt the trackbcipher.txt and enclose a plaintext in your solution. Note that you can use any tools (e.g., openssl) to help you answer the questions. Writing your own program is not necessary. (50 points) 2. A Merkle tree (hash tree) is a tree of hashes in which the leaves are hashes of data blocks in, for instance, a file or set of files. Nodes further up in the tree are the hashes of their respective children. For example, in the picture hash 0 is the result of hashing the result of concatenating hash 0-0 and hash 0-1. That is, hash 0 = hash( hash 0-0 + hash 0-1 ) where + denotes concatenation.Merkle trees can be used to verify any kind of data stored, handled and transferred in and between computers. Currently the main use of hash trees is to make sure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks. Suggestions have been made to use hash trees in trusted computing systems. Answer the following questions: a) Give a specific scenario in which the Merkle tree is used to protect the integrity of the data and explain how Merkle tree is used to protect the security of the message. (I have enclosed a paper in which the Merkle tree is used to protect data security in wireless sensor networks. It is ok to use the paper as an example to answer the question a) and explain how Merkle tree works. However, you are always encouraged to look for other solutions using Merkle tree other than the example given in the paper.) b) For the same scenario, think about a single hash function solution, such as SHA-2. Can you replace the Merkle tree using the single hash function in the scenario given in a)? Why or why not?
INFA723 Homework 1 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. NSA Encrypted Tweet #1url: https://twitter.com/nsacareers/status/463321993878994945?lang=en Cipher text: tpfccdlfdtte pcaccplircdt dklpcfrp?qeiq lhpqlipqeodf gpwafopwprti izxndkiqpkii krirrifcapnc dxkdciqcafmd vkfpcadf. NSA Encrypted Tweet #2 url: https://twitter.com/NSACareers/status/465839250328809472 Cipher text: Rimfinnpeqcnvqauuagcrdokvdisndrdcrpigaisacpsdffaicvhakcfdqfpqdetrkilfaecnpqacakqisacpfampoacfim annicfakdumfalddnraprf NSA Encrytped Tweet #3url: https://twitter.com/NSACareers/status/468399492640034816 Cipher text: nbylcrhspclbyxrnmlbzevsmlchscrhrhnmbebfsvhcxmxxrmzencmfyvychclcmscgmyimkcncxmxrydsmnrhsby emfmmefrhxrfdyrfczmtchmscgby Pick up any encrypted tweet (only one) and answer the following questions: 1. (20 points) What is the plain text? (You can use any tools you have to decrypt the tweet.) 2. (80 points) Write a program (using a programming language at your choice) to decrypt the tweet. The program will read the encrypted tweet from a file, decrypt the tweet, and print the plaintext on the screen. a. Using tools is not allowed in this question. b. Using a static hard coded substitution key, e.g., a key decrypted from a tool, is not allowed. You program needs to conduct cryptography analysis to find the key. All the steps must be done using your own written program. Using a hard-coded substitution key in the program is not a solution for the program (there will be no credit for such solutions). Note: For all the programming assignments, you can choose any operating systems to develop your code. A README.txt is required to submit any programming assignments. In the README.txt, you need to provide the following information: 1) How to compile your program? 2) How to run the program, e.g., usage of program? 3) What is the expected output when running the program? 4) Any descriptions which can help me understand, compile, run, and verify your answers. (FYI: I check every programming assignment turned in!) Zip all you source code, project files, supporting files, and README.txt and submit the all-in-one zip file together to the D2L Dropbox.
The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L.1. This homework includes 2 labs listed as below: (20 points) Lab 9 Use OpenSSL to Generate a Self-Signed Certificate (30 points) Lab 10 Use OpenSSL to Set up a Simple SSL/TLS Server and Test a Remote Host Using SSL/TLS The steps in each lab are documented for your learning purpose. You don’t need to make screenshots for those steps. There is a question section in the end of each lab. Please answer all the questions in each lab. The required data files for the labs have been enclosed in the labs9-10.zip file. Copy the data files to you OpenSSL testing environment to complete the labs. Please create a single document to include all your answers and submit your work through D2L. 2. (15 points) Figure 1 shows a diagram of how to retrieve public keys using a public key authority. In steps 3, 6, and 7, two nonce N1, N2 are used. Explain why N1, N2 are used in the protocol and what security service can be ensured by using N1, and N2 in the protocol. (Hints: think about non-repudiation service in OSI model)Figure 1 Retrieve Public Keys using a Public-key Authority3. (15 points) Users A and B uses the Diffie-Hellman key exchange technique with a common prime q = 71 and a primitive root α = 7. a. (5 points) If user A has private key XA = 5, what is A’s public key YA ? b. (5 points) If user B has private key XB = 12, what is B’s public key YB ? c. (5 points) What is the shared secret key? (Hints: refer to text book Figure 10.1 in Page 303) 4. (10 pints) Consider a one-way authentication technique based on asymmetric encryption: 1. A->B: IDA 2. B->A: E(PUa , R2) 3. A->B: R2 a) Explain the protocol; b) What type of attack is this protocol susceptible to?5. (10 points) Consider the following threats to Web security and describe how each is countered by a particular feature of SSL. a. SSLsplit is a tool for man-in-the-middle attacks against SSL/TLS encrypted network connections. Connections are transparently intercepted through a network address translation engine and redirected to SSLsplit. SSLsplit terminates SSL/TLS and initiates a new SSL/TLS connection to the original destination address, while logging all data transmitted. b. A downgrade attack is a form of cyber attack in which an attacker forces a network channel to switch to an unprotected or less secure data transmission standard. Downgrading the protocol version is one element of man-in-the-middle type attacks, and is used to intercept encrypted traffic. An example of a downgrade attack might be redirecting a visitor from an HTTPS version of a resource to an HTTP copy.
The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. 1. (20 points) Determine gcd(12075, 4655). Don’t forget to include answer for Question 1 in your solution.2. Homework 3 includes 4 labs listed as below: (20 points) Lab5 Use OpenSSL to Generate Random Number and Test Primality (20 points) Lab6 Use OpenSSL to Create RSA Public/Private Key (512bits) without Password Protection (20 points) Lab 7 Use OpenSSL to Create RSA Public/Private Key (4096bits) with Password Protection (20 points) Lab8 A Combination of RSA and AES to Encrypt a File The steps in each lab are documented for your learning purpose. You don’t need to make screenshots for those steps. There is a question section in the end of each lab. Please answer all the questions in each lab. The required data files for the labs have been enclosed in the labs5-7.zip file. Copy the data files to you OpenSSL testing environment to complete the labs. Please create a single document to include all you answers to question 1 and the four labs and submit your work through D2L.
INFA723 Homework 2 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. This homework includes 4 labs listed as below: Lab1 Set up OpenSSL Testing Environment (Optional if you already have an OpenSSL environment) Lab2 OpenSSL Command Line Lab3 Send/Receive a File through a Socket Connection Lab4 Use OpenSSL Crypto Library to Encrypt/Decrypt a File and Send/Receive through a Socket Connection If you already have an OpenSSL testing environment on your computer, you do not need to do Lab1. Go to your Linux terminal, and type command $uname –a and copy the output to a file. Include the output as part of your homework assignment. If you do not have a Linux machine or an OpenSSL environment, follow Lab 1 to set up an OpenSSL testing environment. You can install a Linux virtual machine (e.g., using VMWare Workstation Player) on your windows computer or request a Linux VM from the IALAB. You need an OpenSSL environment before you can continue Lab2, Lab3, and Lab4. For each lab (except Lab 1), there are question sections in the end of the labs. You only need to answer all the questions in each lab. The tutorials in the Labs are for your practice. You don’t need to include screenshots for your practice in the homework solution. All the required data files for the labs have been enclosed in the labs1-4.zip file. Copy these data files to you OpenSSL testing environment to finish the labs. Some of the lab folder includes multiple sub-folders for different versions of the OpenSSL. Based on the OpenSSL version you have, choose the right folder to continue the labs. Please create a single document to include you answers and submit your work through D2L.
INFA723 Homework 1 The homework assignment will be graded based on the following criteria: • Accuracy: 1) the solution meets specific requirements in the problem description; 2) the solution produces correct results; 2) the procedures adopted in the solution are technically sound. • Efficiency: efficiency will be one of the criteria when grading programing assignment. The solution should produce the desired results efficiently. • Effort/neatness: the solution includes excellent effort, and all relate work is shown neatly and organized well. Homework assignment feedback will be available through the DropBox folder on D2L. 1. (10 points) CrypTool (http://www.cryptool.org/) is a free, open-source e-learning application, used worldwide in the implementation and analysis of cryptographic algorithms. The current version offers the following highlights: • Numerous classic and modern cryptographic algorithms (encryption and decryption, key generation, secure passwords, authentication, secure protocols, etc.) • Visualization of several algorithms (Caesar, Enigma, RSA, Diffie-Hellman, digital signatures, AES, etc.) • Cryptanalysis of several algorithms (Vigenère, RSA, AES, etc.) • Cryptanalytical measurement methods (entropy, n-grams, autocorrelation, etc.) • Related auxiliary methods (primality tests, factorization, base64 encoding, etc.) • Number theory tutorial • Comprehensive online help • Accompanying script with additional information about cryptology • And plenty more! The program works in Win32 environment and can be downloaded at http://www.cryptool.org/index.php/en/download-topmenu-63.html. We will use this tool for many class assignments. a) Download CryptTool (v1.4.42) and install it on your computer. b) Encrypt the following message The art of war teaches us to rely not on the likelihood of the enemy’s not coming, but on our own readiness to receive him; not on the chance of his not attacking, but rather on the fact that we have made our position unassailable. —The Art of War, Sun Tzu using Caesar Cipher (Shift-3, C=(p+3) mod 26) and submit your cipher text. c) Decrypt the following messageLw’v hdvb wr xvh!using Casear Cipher (Shift-3, C=(p+3) mod 26) and submit your plaintext.2. (15 points) List and briefly define the six security services as defined in the OSI security architecture.3. (15 points) The following cipher text was generated using a simple substitution algorithm. Nbkyrpsrws jifx. Jir kjqqbofr mssmne tiarp syrqr nbpntgqsminrq bq syr optsr-cjpnr mkkpjmny jc spxbih mff kjqqbofr erxq. Bc syr erx qkmnr bq urpx fmphr, sybq ornjgrq bgkpmnsbnmf. Sytq, syr jkkjiris gtqs prfx ji mi mimfxqbq jc syr nbkyrpsrws bsqrfc, hrirpmffx mkkfxbih umpbjtq qsmsbqsbnmf srqsq sj bs. Eijvi kfmbisrws. Syr mimfxqs gmx or mofr sj nmkstpr jir jp gjpr kfmbisrws grqqmhrq mq vrff mq syrbp rinpxksbjiq. Vbsy sybq eijvfrahr, syr mimfxqs gmx or mofr sj aratnr syr erx ji syr omqbq jc syr vmx bi vybny syr eijvi kfmbisrws bq spmiqcjpgra. Nyjqri kfmbisrws. Bc syr mimfxqs bq mofr sj nyjjqr syr grqqmhrq sj rinpxks, syr mimfxqs gmx arfborpmsrfx kbne kmssrpiq syms nmi or rwkrnsra sj prurmf syr qsptnstpr jc syr erx.Decrypt the message using Cryptool (Hint: combine with manual analysis).4. (15 points) Given a 5×5 matrix for Playfair cipher a) How many possible keys does the Playfair cipher have? Ignore the fact that some keys might produce identical encryption results. Express your answer as an approximate power of 2. b) Now take into account the fact that some Playfair keys produce the same encryption results. How many effectively unique keys does the Playfair cipher have? 5. (15 points) When the PT-109 American patrol boat, under the command of Lieutenant John F. Kennedy, was sunk by a Japanese destroyer, a message was received at an Australian wireless station in Playfair code: KXJEY UREBE ZWEHE WRYTU HEYFS KREHE GOYFI WTTTU OLKSY CAJPO BOTEI ZONTX BYBNT GONEY CUZWR GDSON SXBOU YWRHE BAAHY USEDQ The key used was royal new zealand navy. Decrypt the message using Cryptool. Translate TT into tt.6. (15 points) Using the Vigenere cipher, encrypt the world “explanation” using the key leg.7. (15 points) Meltdown and Spectre exploit critical vulnerabilities in modern processors. These hardware vulnerabilities allow programs to steal data which is currently processed on the computer. Detailed discussions about Meltdown and Spectre can be found at https://meltdownattack.com/ Choose either one of the attacks. Read the paper posted in the website and answer the following questions. a) Briefly describe the attack and the hardware vulnerabilities which make the attack possible. b) What is the general impact of the attack to computer security? The answers should be based on the attack you choose to study. You do not need to cover both attacks.
Submission instructions: Students are to work in groups of two on the assignment. Each group should submit a pdf file that contains the following information: students’ names, students’ IDs, instructions on how to run each file and the associated question solved. Students are also expected to submit a .zip file containing their source code. This code must compile and run without error. The code must be well formatted, commented, and follow the Google Java Style Guide. For more information, see the ECSE420AssignmentSubmissionInstructions.pdf in the Assignment section on myCourses.Questions The following benchmark is designed to measure the average time for reading array A containing L elements from memory, when the array elements are s words apart:for stride s from 4 Bytes (1 word) to L/2 by 2x (s = 1, 2, 4, …, L/2) time the following loop (repeat many times and average) for i from 0 to L-1 load A[i*(s)] from memory (4 Bytes)So, the benchmark reads L words from memory into cache, where L is a constant; however, these L words are not consecutive memory locations (they are “s” words apart).The results obtained from the benchmark are shown in Fig.1:Figure1. Average time for reading each array element.Assuming only one level of cache exists, the cache line size is 4 words, and a single processor is running the benchmark, answer the following questions:1.1 In Fig.1, when the total number of elements L of the array is smaller than L’, the average time per access remains constant. What does the value of L’ represent? What does time t0 show? 1.2 When L is larger than L’, what does time t1 indicate in Fig.1? 1.3 For each part of the graph (i.e., parts 1, 2 and 3), justify its behaviour. 1.4 We know a phenomenon called false sharing could cause unnecessary invalidations in ALock (Anderson Lock), and one way to avoid false sharing is to pad array elements so that 1/2 distinct elements are mapped to distinct cache lines. Considering the results from Fig.1, how could the padding technique used in ALock degrade the overall performance of the lock?2.1. Provide the code for the contains() method missing from the fine-grained synchronization (hand-over-hand locking) algorithm described in chapter 9. 2.2. Write a test to verify the contains() method and explain why your implementation is correct. 3.1. Design a bounded lock-based queue implementation using an array instead of a linked list. Allow parallelism by using two separate locks for the head and the tail. 3.2. Try to transform your algorithm to be lock-free. Where do you run into difficulty? 4.2. Give an efficient and highly parallel multithreaded algorithm for multiplying an n × n matrix A by a length-n vector x that achieves work Θ(n2) and critical path Θ(log n). [Hint: If you use a cached thread pool with the Future interface, to achieve the Θ(log n) critical path, you can follow the algorithm for matrix multiplication in Chapter 16. Otherwise, depending on how you divide-up the problem, you could obtain a critical path different than Θ(log n). This is acceptable, just be sure to show your work and justify in your report the critical path of your implementation.] 4.3. Write a test program that measures the execution time for multiplying a 4,000 by 4,000 matrix with a corresponding 4000 wide vector using the parallel method and sequential method, respectively. Discuss the execution time of the two methods and compute the speedup. Be sure to indicate how many threads are being used. 4.4. Analyze and discuss the work and critical-path length of your implementation and give the parallelism.2/2
ECSE 420: Parallel ComputingSubmission instructions: Students are to work in groups of two on the assignment. Each group should submit a pdf file that contains the following information: students’ names, students’ IDs, instructions on how to run each file and the associated question solved. Students are also expected to submit a .zip file containing their source code. This code must compile and run without error. The code must be well formatted, commented, and follow the Google Java Style Guide. For more information, see the ECSE420AssignmentSubmissionInstructions.pdf in the Assignment section on myCourses.Questions1.1. Implement the Filter lock described in Chapter 2 of the course text. 1.2. Does the Filter lock allow threads to overtake other threads an arbitrary number of times? Explain. 1.3. Implement Lamport’s Bakery lock described in Chapter 2. 1.4. Does the Bakery lock allow some threads to overtake others an arbitrary number of times? Explain 1.5. Propose a test that verifies if a lock works for n-thread mutual exclusion. Provide an implementation for the proposed test and verify if the locks implemented above do provide n-thread mutual exclusion.3.1. Does this protocol satisfy mutual exclusion? (Hint: Start the proof by assuming that two threads A and B are in the critical section at the same time.) 3.2. Is this protocol deadlock-free? Explain. 3.3. Is this protocol starvation-free? Explain.1 class ShakyLock implements Lock { 2 private int turn; 3 private boolean busy = false; 4 public void lock() { 5 int me = ThreadID.get(); 6 turn = me; 7 do { 8 busy = true; 9 } while ( turn == me || busy); 10 } 11 public void unlock() { 12 Busy = false; 13 } 14 } Fig.1 ShakyLock lock protocol used in Question 3.Fig. 2 History AFig. 3 History B5.1. According to what you have been told about the Java memory model, will the reader method ever divide by zero? If yes, describe the order in which writer and reader should be invoked (by threads A and B) and take effect for a division by zero to happen. 5.2. Is division by zero possible if both x and v are volatile? What happens if neither x nor v are volatile? Justify your answer.Fig. 4 Volatile example6.1. If we change the loop at line 11 to “for (int i = x + 1; i < RANGE; i++)”, then the construction is still a regular M-valued MRSW register. Justify your answer. 6.2. If we change the loop at line 11 to “for (int i = x + 1; i < RANGE; i++)”, then the construction yields a safe M-valued MRSW register. Justify your answer.Fig. 5 The regular M-valued MRSW class
Scope and Objective 1. Study the basics of motion control in DC motors Understand the working principle of a DC servo motor and its components Model the DC servo motor as an electromechanical system with feedback control 2. Apply control theory to the design of a motion control system Analysis the conditions for system stability Design the appropriate PID control based on desired transient response specificationsPrelab Exercise Please read prelab reading before coming for the lab. The information on sensors and actuators will be important to your understanding and benefits your learning outcome for this lab.Introduction Motion control is an important application in the automation industry involving an extensive study of system dynamics and control theory. The applications often involve a combination of electrical and mechanical systems to accomplish mechanical work. The DC servo motor is an example of such electromechanical system. The term servo refers to feedback control mechanism which typically comprises components like actuators (DC motors), sensors (encoders) and the controller. In this lab, we will look at motion control. Starting from the understanding of the working principle of the components in the servomechanism through theoretical modeling and physical operations, we will extend the derived model to facilitate the designing of appropriate controllers. This will also pave the path for subsequent lab activities involving the application of the knowledge related to control theory for motion control.Equipment You will be introduced to the DC Servo System (Googol Technology Inc., China) in Control Lab @ ZJUI as shown in Figure 1. This is a servo-system that allows you to acquire hands-on experience in apply the modeling, analysis and design technique you learned in class for motion control.Figure 1: DC Servo System in Instructional Control Lab @ ZJUILab Activities 1. Demonstration of the basics in operating the DC Servo Unit.Figure 2: Closed-loop Test Drive Program (useful for testing and troubleshooting Error)2. Simulation of the model and controller • Try out Section 2 of Chapter X (Googol Technology Inc., China) • At the end of the simulation, your program should allow you to play around with different choices of PID term to intuitively understand the effect of each of themFigure 3: Your completed program should allow you to simulate different parameters3. Implementation of PID controller and analysis on the DC Servo System • Try out Section 3 of Activity Chapter X (Googol Technology Inc., China) • Run ECE486_drive_OpenL and toggle the manual switch to send a ramp input (Figure 4) • Observe the relationship between the voltage input and the output RPM. Given an intuitive explanation to your observation.Figure 4: Input voltage and the output rpmChapter X PID Calibration1．Calibrate the DC servo motor system with PID method; 2．Design and verify such calibrated link. II. Experiment Requirements 1. Based on the given performance index, use trial-and-error method to design the PID calibration link, and calibrate the uncorrected ones, then verify such calibration. 2. Set the open-loop transfer function of the uncorrected system as G 0 (s) , then design the PID calibration link, and make the performance index of the system reach ts 1.5 s, p 4.3% , and static error 0. III. Experiment Device 1. GSMT2014 DC servo system control platform; 2. PC and MATLAB platform IV. Experiment Principles 1. PID introduction There are various control algorithms of PID, with each aiming at one specific filed. The Fig. 10.1, Fig. 10.2 and Fig. 10.3 present three different algorithms. In simulating control system, the most commonly used control law is PID control. The simulated PID control system block diagram is shown as Fig. 10.1, and the system is composed of simulated PID controller and object.Fig. 10.2 Differential Antecedent PID Control Schematic DiagramFig. 10.3 Puppet PID Control Schematic Diagram As a kind of linear controller, the PID controller shall constitute control deviation e(t ) between the given value r (t ) and actual output value y (t)e t( ) r t( ) y t( ) （10.1） The PID controller is so called because it combines ProportionP , Integral I with DifferentialD of the deviation via linear means, and constitutes the control variable to have the object controlled. The law is:t 1 de (t) u (t) K P e(t) I 0 e(t)dt T D dt （10.2） T Or in the form of transfer function: U (s) 1 G (s) K P 1 T D s E (s) T I s （10.3） Where, K P means proportion coefficient, T I integral time constant, and T D differential time constant. In control system design and simulation, the transfer function is also written in the form of:U (s) K I K D s 2 K p s K I G (s) K P K D s E (s) s s （10.4） Where, K P means proportion coefficient, T I integral coefficient, and T D differential coefficient. Seen from the standpoint of root locus, formula (2.10) is equivalent to adding a pole located at base point and two null points with variable location to the system.To be simple, each calibration sector of the PID controller works as below: A. Proportion sector: it reflects the deviation signal e(t) of the control system in proportion, the controller shall work as soon as the occurrence of the deviation to reduce it. B. Integral sector: It is mainly used to eliminate the static error and improve system type level. The role of integral is positively correlated to the integral time constant T I . C. Differential sector: It reflects the change trend (change rate) of the deviation signal, introduces an effective early correction signal into the system before the deviation signal enlarges, so as to speed up the process speed and shorten tuning time.2. Tuning of PID parameters with trial-and-error method Set the structural diagram of the DC servo motor’s control system as the figure below:At the input speed of 2000rpm, the performance index of the uncorrected system is: static value 1000rmp, static error 50%, overshoot , tuning time s. The PID calibration link is required to design with the trial-and-error method to tune the parameters, then ts 1.5 s, p 4.3% , and static error 0.V. Experiment Procedures 1. Simulink simulation of uncalibrated system3) In the “Simulink Library Browse” window, open the “Simulink Continuous” window, as shown below:4) Drag the “Transfer Fcn” module into the newly created “untitled” window:5) Double-click the “Transfer Fcn” module and open the following window. The parameters are set as follows:6) Right-click on the “Transfer Fcn” module and set “Background Color” to Cyan.7) Another copy of the “Transfer Fcn” module, double-click to set the parameters as shown in the figure below, and set its background color as Green8) Drag from the “Simulink Sinks” a “Scope” to “untitled” window:9) Open” Scope”, click , and check “Save data to workspace” . Set “Variable name” to user-defined, and “Format” to Array.10) Drag from the ” Simulink Commonly Used Blocks ” a “Sum” to “untitled” window:11) Double-click the “Sum” module and open the following window. The feedback setting is as follows:12) Drag from the ” Simulink Sources ” a “Step” to “untitled” window, and set the Final Value is 200013) Connect the five modules as shown below and save the file as ” UncorSys_Sim ” with the default format of MDL.15) The closed loop system is stable with a steady-state value of 1000rpm, a steady-state error of 50%, overshoot amount of , and adjustment time of seconds.2. Build the system simulation program with calibration link in the Simulink as shown below: 1) Drag a “Subsystem” from Simulink Library module to UncorSys_Sim. MDL.2) Open the Subsystem module, build PID module. First, three Gain modules were dragged into the page from “Simulink Library Commonly Used Blocks” and were named Kp, Ki and Kd respectively.3) Drag “Derivative” and “Integrator” from “Simulink LibraryContinuous” to the page.4) Drag a “Sum” from “Simulink Library Commonly Used Blocks” to the page.5) Double-click the “Sum” module to open the following window, and the feedback Settings are shown below:6) Connect each module according to the following figure, open three modules of Kp, Ki and Kd, and set their Gain value to Kp, Ki and Kd.8) Right-click on the PID module and select the “Edit Mask” panel. Set the encapsulated module properties as shown in the figure below.9) Right-click on the PID module and set the module “Background Color” to “Orange”. The final control program is shown in the figure below.10) Save the file as PID_Sim.mdl.Double-click to open the PID module, set Kp=0.4, Ki=4.5, Kd=0.11) Click the button “ ”，and double click Scope module to get system simulation curve.12) The overshoot rate was 1.4%, the adjustment time was 0.536 seconds, and the steady-state error was 0. Meet system design requirements.3. Real-time control of the system after adding PID correction 1) Turn on the power button on the electric cabinet of dc servo control platform. 2) Open the file “PID_CorSys_Ctrl.mdl” in MATLAB/Current Folder and the real-time control interface will pop up as shown in the figure.3) Set PID parameters as: Kp=0.4, Ki=4.5, Kd=0. 4) As the maximum motor speed is 3000rpm, the step signal cannot be too large or too small, so it is appropriate to take 1000-2000rpm. This experiment took 2000 rpm. 5) Select “Simulation/Configuration Parameters”, then the following window will pop up. Click “Solver” in the left property tree, set “Type” to fixed-step, and set size to 0.01. Also, set “Solver” to “ode1 (Euler)”. ” to compile the program. After successful compilation, there is a prompt message in the MATLAB command window (if the control interface structure is not modified, it is not necessary to carry out this step after compiling again):7) control box is connected. 8) Click “ ” to run the procedure, and motor start. Let it run for about 10 seconds, and then click “ ” stop. 9) Double-click “Scope” to open the oscilloscope and observe the dc servo motor speed response curve when , peak time t p , the step signal of 2000rpm is added. Measure and calculate the system overshoot adjust time t s ,and fill in the test record form.VI. Experiment Records Controller Parameters Performance Index Uncorrected System None Static value is 1000rpm, and static error is 50% s Correction System Simulation Kp=0.4, Ki=4.5, Kd=0 s The static error is 0 Correction System Measurement Kp=0.4, Ki=4.5, Kd=0 s The static error is 0VII. Experiment Analysis 1. How to determine the PID controller’s parameters? 2. Why the PID control is widely used in industrial application?
ECSE 420: Parallel Computing Submission instructions: Students are to work in groups of two on the assignment. Each group should submit a pdf file that contains the following information: students’ names, students’ IDs, instructions on how to run each file and the associated question solved. Students are also expected to submit a .zip file containing their source code. This code must compile and run without error. Sample codes are provided for Questions 1&3; students just need to modify these sample codes. The code must be well formatted, commented, and follow the Google Java Style Guide. For more information, see the ECSE420AssignmentSubmissionInstructions.pdf in the Assignment section on myCourses. Questions 1.1. Modify the following method in the sample code to Implement a matrix multiplication sequentially: public static double[][] sequentialMultiplyMatrix(double[][] a, double[][] b) Explain how you validate the method produces the correct results. 1.2. Modify the following method in the sample code to Implement a matrix multiplication in parallel: public static double[][] parallelMultiplyMatrix(double[][] a, double[][] b) Explain the parallel tasks defined in your code and how their results are combined to produce the correct results. Explain how you validate the method works correctly. 1.3. Add a method to the source code that measures the execution time for both sequential and parallel matrix multiplication. 1.4. Vary the number of threads being used by the parallel method for matrix sizes of 2000 by 2000 and plot the execution time as a function of the number of threads. 1.5. Vary the size of the matrices being multiplied as (100 by 100, 200 by 200, 500 by 500, 1000 by 1000, 2000 by 2000, 3000 by 3000, 4000 by 4000) and plot the execution time as a function of matrix size for both parallel and sequential methods in one figure. Use the number of threads for which the parallel execution time in 1.4 is minimum. 1.6. For the generated graphs in 1.4 and 1.5 comment on their shape and possible reasons for the observed behavior.2.1. Explain under what conditions deadlock could occur and comment on its possible consequences. 2.2. Discuss possible design solutions to avoid deadlock.1/2Figure 13.1. Modify the class public class DiningPhilosophers in the sample code to simulate the behavior of the philosophers for any number n of them, where each philosopher is a thread, and the chopsticks are shared objects. Notice that you must prevent a situation where two philosophers hold the same chopstick at the same time. Notice that in this program philosophers should be eventually deadlocked. 3.2. Amend your program so that it never reaches a state where philosophers are deadlocked, that is, it is never the case that each philosopher holds one chop- stick and is stuck waiting for another to get the second chopstick. Explain your solution to avoid deadlock. 3.3. Amend your program so that no philosopher ever starves. Explain your solution to avoid starvation.4.1. Suppose the sequential part of a program accounts for 40% of the program’s execution time on a single processor. Find a limit for the overall speedup that can be achieved by running the program on an n-processor machine. 4.2. Now suppose the sequential part accounts for 30% of the program’s computation time. Let sn be the program’s speedup on n processors, assuming the rest of the program is perfectly parallelizable. Your supervisor tells you to double this speedup: the revised program should have speedup s′n > sn*2. You advertise for a programmer to replace the sequential part with an improved version that decreases the sequential time percentage by a factor of k. What value of k should you require? 4.3. Suppose the sequential time percentage could be decreased 3-fold, and when we do so, the modified program takes half the time of the original on n processors. What fraction of the overall execution time did the sequential part account for? Express your answer as a function of n. 2/2
