2019 Spring, CSCI 3150 – Assignment 2Contents1 Introduction 31.1 Permissible Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Grading 42.1 Correctness (100%) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Bonus (25%) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Your assignment 53.1 The assignment package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2 To begin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2.1 Run our grader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2.2 Run our demo (in case you want to try the bonus) . . . . . . . . . . . 83.3 Your job . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Change Log 105 Questions 1016 Academic Honesty 117 General Notes 1121 IntroductionIn this assignment, you have to implement a part of a “permissible” scheduler that returnsa set of “permissible” jobs from a large batch of jobs submitted to an operating system. Apermissible scheduler aims to execute only jobs that are meaningful to the system (becauseof limited resources). You must use PThread/OpenMP to leverage multiple cores to returnthe answer as quick as possible.1.1 Permissible PointA task/job/process is modeled as a data point. Given a multi-dimension dataset, a set ofpoints are regarded as the permissible points if they are not prevailed by any other points.Under the assumption that smaller values are better, a point p prevails another point q if(i) all dimensions of p are smaller than or equal to their corresponding dimensions of q and(ii) there exists at least one dimension of p that is strictly smaller than its correspondingdimension of q. Thus, the set of permissible points consists of those points that areno worse than any other points when all dimensions are considered together. Forexample, given the following 3-dimension (excluding ID) dataset:ID dimension 1 dimension 2 dimension 31 0.1536 0.5631 0.78532 0.2534 0.5315 0.47353 0.1235 0.3436 0.98134 0.5343 0.5674 0.87535 0.6437 0.7832 0.12356 0.4536 0.3134 0.33427 0.6582 0.3253 0.92318 0.4536 0.3134 0.43539 0.1536 0.5631 0.7853 Point 1 prevails point 4 because all dimensions of point 1 are smaller than theircorresponding dimensions of point 4.3 Point 6 prevails point 8 as dimension 3 of point 6 is smaller than correspondingdimension of point 8, although their other two dimensions have the same values. Point 1 and point 2 cannot prevail each other, because dimension 1 of point 1 issmaller than corresponding dimension of point 2, but dimension 2 and dimension 3of point 1 are greater than corresponding dimensions of point 2 and vice versa. Point 1and point 9 cannot prevail each other either, as all dimensions of them are equaivalent.From the above dataset, we can retrieve points 1, 2, 3, 5, 6, 9 as its permissible points.In real life, a job/task/process might have dimensions like estimated CPU time required,estimated I/O required, etc.2 Grading2.1 Correctness (100%) There is a toy test case for you, the number of points is very small, you could use thatto do simple testing and debugging. There are 10 test cases to check whether your program have correctly computed theanswers. Different test cases will generate data different in sizes, dimensions, and data distribution,and will invoke your program with the generated dataset. Each test case worths 10 marks, and the toy test case worths 0 marks.2.2 Bonus (25%)There are 2 extra bonus test cases for those having good performance. If your program’sreal-time1in maximum speed (i.e., using all 4 cores) finishes faster than: (5%) our demo using 3 threads (cores), you get 5 marks extra bonus. [bonus test case1]1For multi-threading program, we shall not use user-time + sys-time because the threads are overlapping.4 (20%) our demo using 4 threads (cores), you get another 20 marks extra bonus. [bonustest case 2]To eliminate any rounding error, if your program’s running time is within our demorunning time ±5%, we will run both programs 10 times and compare the average. The TAwill not launch any other unnecessary processes while grading.2.3 Note The TA will grade the latest version in your repo as of 25 April 2019, 11:00AM. Thatis the latest date. No late submission after that. For this assignment, you shall and we will set our course VM to have: (1) Base memorysets to 1G; (2) The number of processors sets to 4.Especially, our test has a data generator that is hardware dependent. As the expectedoutputs in our tester are hard-coded based on the given course VM, you may not passthe test (even your code is correct) if you are running on another platform. So, runon our VM. You must parallelize the workload to all processors/cores in a reasonable manner.For example, an implementation that locks the whole program and let each threadexecute one by one is not acceptable.3 Your assignmentYou are given the following files:5Name Description/asgn2-pthread.c Code skeleton for you (Work on it)./Makefile Makefile (Don’t touch)/pthreaddemo Executable demo. Beating it can get the bonus./testcase (Don’t touch) testsuite.txt lists the test casesand the other files contain the expected output ofeach test case./runtest.c (Don’t touch) Our grader. It will use CUnit to runthe test. It will invoke the asgn2 pthread functionin your asgn2-pthread.c./util.h (Don’t touch) Contains some utility data structure./util.c (Don’t touch) Contains some utility functions includingthe point dataset generator.Note: The above assumes the course’s 32-bit (4 virtual CPU enabled) VM is used.3.1 The assignment packageFollow the steps in section 2.1 of assignment 0 to report your Github account (if you havenot done so yet), and go here https://classroom.github.com/a/aOFOFMh1 to clone thestarter package to your Github account. After this, in your terminal use the command “gitclone {Your Repo URL}” and your username/password to get a local copy of the repo toyour desired directory in the same way as described in assignment 0. The new repo shouldcontain the starter package for this assignment.Warning: DON’T change the file names, otherwise you get 0 marks3.2 To begin3.2.1 Run our gradermake./runtestYou will see:6 Type ’0’ to run the toy test case. Type ’1’ - ’12’ to select a test case to run. Type ’13’ to run all 13 test cases.Before you work on your homework and type ’13’ to run all 13 test cases, you shall seesomething like below, because no test cases can pass yet.After doing the assignment, if your solution is correct and you type these two commandsone by one:make7./runtestyou shall see something like this:Warning: The elapsed time within the red rectangle in above picture is not correct (CUnit has not supported threading wellyet), so just ignore it. The time cost per individual test case is accurate.3.2.2 Run our demo (in case you want to try the bonus)We give you our implementation of the assignment, pthreaddemo. You can run it in astandalone mode. If you type these two commands one by one:chmod a+x ./pthreaddemo./pthreaddemo helpYou will see its usage.8It will either compute the results for bonus test case 1 or bonus test case 2 and it tells youour demo’s running time on your machine. You may refer to that running time as yourtarget to get the bonus score.3.3 Your jobYour job is to start from the given asgn2-pthread.c and pass as many test cases as possible.Don’t change the function signature asgn2 pthread. We explain some items in that file: Point is a C structure including an integer, ID, and a float pointer, values, which isdefined in util.h. That is the data structure we use to represent a (generated) datapoint. thread number: control how many threads used to run your code. The main threaddoesn’t count. So, you shall use PThread to create thread number extra threads tospeed up your job. Your program should store all the permissible points in a Point array2, and set thevariable permissiblePoints the pointer to that array. The Point array should be in2The order of permissible points does not matter. The CUnit test program will sort the permissible pointsbased on ID when grading. The sorting won’t count towards the running time.9heap. Your code should also set the variable permissiblePointNum as the number ofpermissible points found. In the comment, there is a for-loop. You may uncomment it to print the content offirst 20 points. That may get you a quick feeling about how the point dataset is storedin the memory.[Minor] For your information, /testcase/testsuite.txt contains 13 lines. Each linespecifies the parameter values of one test case. The 1st value is the number of data points to be generated The 2nd value is the number of dimensions to be generated. The 3rd value is the data characteristic for the data to be generated. The 4th value is the random seed that we use to generate random data. The 5th value is the number of threads (excluding the main thread) to use. The last value is the path to the expected result of the generated data.[Minor] For your information, /testcase/* result.txt contains the expected result ofeach test case. It lists the number of permissible points in the first line. Each subsequentline lists the ID of the permissible points in ascending order. The CUnit test program willread this file to check the output produced by your code at runtime.4 Change Log1.0 this document5 QuestionsIf you have doubts about the assignment, you are encouraged to ask questions on Piazzausing the corresponding tag. Please focus on knowledge. Unhealthy questions/commentsthat focus on scores and grades are not encouraged.10If you find any (possible) bugs, send private questions on Piazza to us instead— otherwise that may cause unnecessary panic among the class if that is not a real bug.6 Academic HonestyWe follow the University guide on academic honesty against any plagiarism.7 General Notes This specification and our grading platform are both based our given course VM. Youshould compile, debug and run the assignment program on that VM. So, if you insistto develop on another platform other than our VM and got any question, test it onour VM before you ask. The TA reserves the right to adjust your scores for any request that requires their extramanual effort. Unless specified, you should work and fill your code in designated areas. There arecases that the modification outside the designated area leads to misbehavior of the autograder. Proceed with caution and look back the changes if your output is different fromwhat is shown in the grader. While we have already tried our best to prepare this assignment, we reserve all therights to update the specification and the grading scheme. If there are any mistakes/bugswhich are on ours, the TA will step in and do manual grading to ensureyou get what you deserve. Please respect each other. Any irresponsible, unfair, biasedsentiment would regard as a disciplinary case. If this is a programming assignment, only C is allowed, not even C++. If this is ascripting assignment, only bash shell script is allowed, not even Python. Furthermore,for C programming assignments, use the “exit” function parsimoniously because itmight influence the grader as well. Therefore, use “return” instead of “exit” wheneverpossible.11? Although this is not an algorithm class, you still shouldn’t implement your assignmentwith very poor complexity. While the TAs will try their best to run your program aslong as they could, they reserve the right to terminate a test case and regard that as afailed test case when a program takes unreasonably long time to finish (try to compareyour running time with the given demo). or until when the TAs themselves need tosubmit your final scores to the department. When grading, the TAs will execute the grader program to run the whole test suite(which consists of all test cases). The TAs won’t grade each individual test caseseparately. (Frequently Asked) [Output format] If the assignment package includes a demo,then our grader defines test cases based on the given demo. In that case, your outputshall exactly follow that demo. For example, hypothetically, if our demo outputs amessage like:command not foundwith two spaces between “not” and “found”. Your output shall also match that inorder to pass the test. The good news is that, if our given demo has not implementedsomething (e.g., missed certain error checking), you also don’t need to do so. Notest cases would be defined based on something that our demo has notimplemented. (Frequently Asked) [Scope of error handling] The scope of error checking andhandling shall refer to both our given demo (if given) and our given test cases.First, the corresponding output message shall exactly follow our demo. Second, youare informed that our demo may have implemented more error checking that what ourgrader will test. In that case, it is fine that you implement only the error checking thatis tested by our grader. So, one top tip is:CHECK THE (SOURCE OF)12TEST CASES BEFORE YOU ASK (Frequently Asked) [No hidden test case] We are not intended to run any secret/extratest cases that deliberately break your assignment. That is, WYSIWYG — yourfinal score shall be generally indicated by what the grader reports when it runs onthe course VM. However, we do reserve the right to run some additional test cases toavoid any mis-conduct (e.g., hard-coding the results), and/or invite you to explain thesource code to the teaching assistants and adjust the scores accordingly. We welcome discussions among classmates. But don’t share your assignment with theothers in any means. For example, don’t put your source code in any public venue (e.g,public repo, your homepage, Facebook). We handle plagiarism strictly. On submittingthis assignment, you are agreed that your code’s copyright belongs to the ChineseUniversity of Hong Kong. Unless with our written approval, you must not releaseyour source code and this specification now and forever. If you share your code withanyone without our written consent, that would regard as a disciplinary case as longas you are still a CUHK student (i.e., even after this course). If you share your codewith anyone without our written consent after your graduation, that would regard asa breach of copyright and we reserve all the rights to take the corresponding legalactions. Google is your friend. We encourage you use Google for help to do the assignment.However, if you happen to find any source codes related to this assignment, you stillcannot copy it but use your own way to implement it. You need to put down your listof source code references as comments in the top of your source code. (Frequently Asked) [Late Policy] TAs will only grade the latest version submittedbefore the deadline. Since you are given way more enough time (especially for earlyassignments), no late submission is allowed. It is your responsibility to make sure youadded, committed, and pushed the find version before the deadline. You are requiredto check whether your final version is really in Github Classroom.13本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论