Version: 1.0 Changelog1 Rules • Read the entire document before starting. Critical pieces of information and hints might be provided along the way. • Unfortunately, experience has shown that there is a high chance that errors in the project description will be found and corrected after its release. It is your responsibility to check for updates on Canvas, and download updates if any. • Make sure that all your code is written according to C11 or C++20 standards, using only the standard libraries. 2 Introduction This project will have you implement the agent and directory controllers for some cache coherence protocols on a multiprocessor. The underlying notion is straightforward: all caches must see all writes on a piece of data in the same order. The implementation of this idea is obviously not so simple (otherwise we probably wouldn’t have a project on it!). Your modifications to the simulator framework will maintain coherent caches for the MSI, MESI, MOSI, and MOESIF protocols using a directory-based approach. You are provided the agents for MSI and MOSI, and the directory controllers for MESI, MOSI, and MOESIF. You will need to implement the agents for MESI and MOESIF, and the directory controllers for MSI. Your simulator will simulate systems with 4, 8, or 16 processors (cores) and will need to ensure that coherence is maintained. You have a completed/working pair of agent and directory for MOSI. 50% of each of the remaining protocols has been implemented and as such this project is not expected to be as difficult or time consuming as the other projects in this course once you understand how directory based coherence works. Detailed comments have been provided in the directory files you need to implement. The agent transitions are available in Appendix C Note: This project MUST be done individually. Please follow all the rules from Section 1 and review Appendix A. 3 Simulator SpecificationsFigure 1: System Overview 3.1 Simulator Overview This section details some of the specifics of the provided code in simulator/. Deeper implementation details are not covered in depth since they should not affect your work in the coherence/ directory. Remember that you are not going to be simulating data values at any point in the simulation. 1. The system consists of 4, 8, or 16 processors (cores). Each core is essentially a memory trace reader that will read in the provided trace files. You will not need to modify these structures. 2. For the sake of simplicity, each core has a single L1 cache that is fully associative, infinite sized, and has a single cycle access latency. The code for this cache is provided. These caches are not coherent as of now, so you will need to implement the agents and directory controllers to make the caches coherent. 3. The system has a single memory controller which accesses the off-chip memory with a 100 cycle latency. The centralized directory is kept at the memory controller and responds to one request/message per cycle. If the data is not stored at any of the caches or if the data needs to be read from memory, the 100 cycle DRAM access penalty must be paid. You will be implementing the directory controller for the MSI coherence protocol. 5. Each processor (trace reader) will have up to one outstanding memory request at a time. The processor sends its request to the cache and will wait until the cache responds with a DATA message using send DATA proc(). The caches will maintain coherence using the ring network and the directory. 6. We have provided a full simulator framework in C++. The only files you will need to modify are in the coherence/ directory. 7. As a reminder, you will need to implement the agents and directory controllers in: MSI directory.cpp, MESI agent.cpp/hpp, MOESIF agent.cpp/hpp • When a processor makes a request for the cache, the cache will find the cache entry then call the appropriate process cache request() for the protocol/agent being used. This function should look at a cache entry’s state and determine which messages (if any) should be sent on the network, and which state to transition to. The function is already set up to call the appropriate do proc XX() helper functions that have been stubbed out for you. • When a request is encountered from the network, the cache will find the appropriate cache entry and call process ntwk request() for the appropriate protocol/agent. This function should look at a cache entry’s state and determine which messages (if any) should be sent on the network, and which state to transition to. The function is already set up to call the appropriate do ntwk XX() helper functions that have been stubbed out for you. • When the directory controller receives a message, it should modify the state in the directory as needed and send any messages required to maintain the state. The directory controller will call the appropriate PROTOCOL tick() function, which has been stubbed out for you. • You should not need to modify any of the header files provided to you and should not need any more state tracking variables than those already in the simulator infrastructure. Note: In order to properly interface with the simulator infrastructure, do not change any class names or delete any functions. 3.2 Simulator Assumptions 2. The input queues on each node are treated as FIFO in most cases. However, if a request cannot be processed in the current cycle (e.g. the corresponding entry is in a transient state and waiting for a reply from another node), pop this request and push it back to the end of the queue using cycle queue(), this is done to avoid possible deadlocks. 3. If we are reading from memory, the other requests in the directory queue cannot be processed. The directory is stalled until the memory operation completes. In this case, we do not push the request to the back of the queue. In essence, we simply stall the input queue until the memory read completes. We do not need to wait for writebacks to complete (e.g. there is an infinite on-chip store buffer to DRAM). You can directly forward the data to the requester from the directory controller. 3.3 Directory Implementation 2. In general, there is more than one way to implement each protocol. For this project, the reference implementations were made with simple logic, emphasizing cache-to-cache transfers, and running in minimal time, so please follow the instructions in this PDF instead of Wikipedia. 3. In order to simplify the simulator, all $-to-$ transfers will first have a node send DATA to the directory, then the directory controller will forward the data to the destination. 6. You should not need to allocate or free any structures, the helper functions in simulator/agent.h and send Request in the directory should handle all allocations and sending of messages. You just need to provide them with the right arguments. More documentation is provided in the source code. 3.4 Library of Messages There are a number of messages that will be used in the simulator infrastructure. They can be found in coherence/messages.h • LOAD: The CPU sends the cache agent this message to service a load in the trace. The cache will handle this by either sending the data to the CPU (if in M, S, E, F, or O) or by sending a GETS on the network. • STORE: The CPU sends the cache agent this message to service a store in the trace. The cache will handle this by either sending the data to the CPU (if in M) or by sending a GETM (GETX if in E state) on the network. • GETS: Get with intent to Share. This request informs the directory that the requester wants to read from the address. • GETM: Get with intent to Modify. This request informs the directory that the requester wants to write to the address. • REQ INVALID: The directory will request a cache agent to go to the I state with this message. The agent should either go to I or the appropriate transient state when it sees this message and send INVACK. • INVACK: The cache agent should respond to REQ INVALID with this • DATA E: The directory will respond to a cache agent with this when the cache should go to state E instead of state S since the cache is the exclusive sharer • RECALL GOTO I: The directory uses this message as a mechanism to initiate cache to cache transfers • RECALL GOTO S: The directory uses this message as a mechanism to initiate cache to cache transfers • There are other messages defined in the message t enum, but they are not used for this project. 3.5 Cache Agent State Transition Diagrams See Appendix C for details on the Agents for each of the protocols. They should help you understand the variety of messages you should expect to send and receive for each protocol. 3.6 Simulator Parameters The following command line parameters can be passed to the simulator: • -p: The protocol that the simulator will be using (MSI, MESI, MOSI, and MOESIF). • -t: The path of a directory containing the memory access traces for each core. For example, you could pass -t traces/core 4 . • -n: The number of processors. To determine this value, note the number of files in the individual trace directory determine how many cores you need to run the simulator with. • -h: Print the usage information 3.6.1 Additional Parameters The following parameters are available but not implemented and you should not modify them: • -c: CPU Type: Only FICI In-Order CPUs are supported for now • -i: The interconnect topology. For this project, only a simple RING network is supported • -l: The link latency. For this project, each message only takes 1 cycle to take a step along the ring. In a real system, DATA messages could take many more cycles • -m: The memory access latency. For this project, each memory request takes 100 cycles. 4 Statistics We are concerned with the following statistics, which need to match exactly. • sim->clock: Execution time in simulator cycles (The provided code manages this for you). • sim->cache misses: Counts when a CPU makes a request and the cache is in state I. • sim->cache accesses: The number of times the CPUs attempt to access the cache (The provided code manages this for you). • sim->silent upgrades: The number of silent upgrades for the MESI and MOESIF protocols. • sim->cache to cache transfers: The number of times data is provided by another cache and we do not have to go to memory. • sim->memory reads: The number of times we went to memory to access data (The provided code in the directory controller manages this stat for you but you still need to set up the directory controller correctly). • sim->memory writes: The number of times the directory received dirty data that needed to be written to memory. Like previous projects, you can run make validate to compare with the reference outputs. 5 Implementation Details You will need to modify the following files in coherence/: • directory/MSI directory.cpp – Where you will implement the directory controller for the MSI protocol. • agents/MESI agent.cpp – Where you will implement the per core agent for the MESI protocol. • agents/MOESIF agent.cpp – Where you will implement the per core agent for the MOESIF protocol. You are encouraged to look at the pieces of the protocols that have been provided to help you understand how the agents/directories work. Additionally, to avoid confusion from hanging simulators, we have added a check that exits the main simulation loop if the simulation has been running for 500,000 cycles. No simulation in this project should even approach that cycle count. If you see the message “is there a deadlock?” when running your code, please ensure that your code is not stuck in a transient state. 5.1 Docker Image We have provided an Ubuntu 22.04 LTS Docker image for verifying that your code compiles and runs in the environment we expect — it is also useful if you do not have a Linux machine handy. To use it, install Docker (https://docs.docker.com/get-docker/) and extract the provided project tarball and run the 6290docker* script in the project tarball corresponding to your OS. That should open an Ubuntu 22.04 bash shell where the project folder is mounted as a volume at the current directory in the container, allowing you to run whatever commands you want, such as make, gdb, valgrind, ./dirsim, etc. 5.2 Important Note the project run time, en sure that your code val idates lo cally with this flag. It is help ful to treat all warn ings as er rors. En sure you use the docker con tainer even if you didn’t need it for past as sign ments. 6 Validation Requirements You must run your simulator and debug it until the statistics from your solution perfectly (100 percent) match the statistics in the reference outputs for all test configurations. This requirement must be completed before you can proceed to Section 7 (Experiments). You can run make validate to compare your output with the reference outputs. If you want to test only one protocol for all traces, you can use the validate.sh script directly and pass it a protocol name, like ./validate.sh MSI. 6.1 Debug Outputs You are strongly encouraged to use the debug outs as they will help you see exactly when the simulator state differs between the solution and your implementation. These debug outs are how we debugged and validated the simulator and should contain all the information required to find a bug. Please do not submit code that always generates debug outputs or other print statements, as this will break the autograder and cause you not to match reference outputs. 6.2 Debugging 7 Experiments Once your simulator has been validated and matches the ref outs, you will run the experiments in the experiments/ directory included in the assignment tarball. Compare the performance of each experiment using the MSI, MESI, MOSI, and MOESIF protocols. You should run all experiments with 8 cores (-n 8). Provide the execution time in cycles for each configuration. Using the simulator statistics and any other information from the course or your own research, explain why a certain protocol performs better for a certain experiment. Pick the best protocol for each experiment. Ensure that the report is in a file named report.pdf. Please submit a PDF and not other file types (no Microsoft Word documents, please). 7.1 Experiment core counts You have been provide benchmarks to run for 8 cores: • array sum – arrayblock – array stripe • matrix multiply (matmul) – matmul row – matmul col • map reduce • pipeline migrating You are provided the source code for each of the benchmarks under experiments/programs, and your analysis will need to consider the behavior of each benchmark when explaining results. The top of each source file explains what the program does. The traces for each benchmark contain the instruction fetch and load/store/atomic accesses for the worker threads. For each benchmark, run experiments for 8 cores (-n 8), and pick the protocol (MSI, MESI, MOSI, or MOESIF) that takes the fewest total cycles. Look at the source and explain why the chosen protocol outperforms the other protocols. For the array sum benchmarks (array block and array stripe), explain why the performance differs even if the same protocol is chosen for both. For the matrix multiplication benchmarks (matmul rows and matmul cols), explain why the performance differs even if the same protocol is chosen for both. Your report should contain (at least) the following sections 1. Array Sum (a) Array Block (b) Array Stripe 2. Matrix Multiply (a) MatMul Rows (b) MatMul Cols 3. Pipeline 4. Map-Reduce 8 What to Submit to Gradescope Please run make submit and submit the resulting tarball (tar.gz) to Gradescope. Do not submit the assignment PDF, traces, or other unnecessary files (using make submit avoids this). Running make submit will include PDFs in the project directory in the tarball, but please make sure that the command ran successfully and your experiments report PDF is present in your submission tarball. We will create a simple Gradescope autograder that will verify that your code compiles and matches the 10 million–branch gcc trace and a subset of the other reference traces. This autograder is a smoke test to check for any incompatibilities or big issues; it is not comprehensive. Make sure you untar and check your submission tarball to ensure that all the required files are present in the tar before making your final submission to Gradescope! 9 Grading You will be evaluated on the following criteria: +50 : You turn in well commented significant code that compiles and runs but does not match the validation +10 : Your simulator completely matches the validation outputs for MSI +10 : Your simulator completely matches the validation outputs for MESI +15 : Your simulator completely matches the validation outputs for MOESIF +15 : Your experiments have been run and your report is of high quality• Copy/share code from/with your fellow classmates or from people who might have taken this course in prior semesters. • Publish your assignments on public repositories, github, etc, that are accessible to other students. • Submit an assignment with code or text from an AI assistant (e.g., ChatGPT). • Look up solutions online. Trust us, we will know if you copy from online sources. Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct. Appendix B – Helpful ToolsYou might the following tools helpful: • gdb: The GNU debugger will prove invaluable when you eventually run into that segfault. The Makefile provided to you enables the debug flag which generates the required symbol table for gdb by default. – You can invoke gdb for the with gdb ./dirsim and then run run -i traces/ at the gdb prompt. • Valgrind: Valgrind is really useful for detecting memory leaks. Use the following command to track all leaks and errors for the simulator: valgrind –leak-check=full –show-leak-kinds=all –track-origins=yes ./dirsim -i traces/ • Address Sanitizer: This is similar to Valgrind, but often runs faster and can detect more issues. Compile your project with make ASAN=1 to use it. Appendix C – Cache Agent State Transition DiagramsIt is important to note that CPU side messages that do not change state are not shown in these diagrams. Messages that are sent by the cache agent (whether to the CPU or to the directory) are also not shown:Figure 2: MSI Cache Agent State Transition DiagramFigure 3: MOSI Cache Agent State Transition Diagram.Figure 4: MESI Cache Agent State Transition Diagram.Figure 5: MOESIF Cache Agent State Transition Diagram.
Multithreading Foreword In this project, you will design and implement a multi-threaded server that serves static files based on the GetFile protocol, which is a simple HTTP-like protocol. Alongside the server, you will also create a multi-threaded client that acts as a load generator for the server. Both the server and client will be written in C and be based on a sound, scalable design. Setup Please follow the instructions given in the environment repository for setting up your development/test environment. You can clone the code in this repository with the command $ git clone https://github.gatech.edu/gios-spr-25/pr1.git Submission Instructions We use an auto-grading system based upon Gradescope. You can find Gradescope from Canvas, and that will make the submission engine available to you. You will need to manually upload your code to Gradescope, where it will be executed in its own environment (a Docker container) and the results will be gathered up and returned to you. Feedback from Gradescope Note that there is a strict limit to the amount of feedback that we can return to you. Thus: We do not return feedback for tests that pass We truncate any feedback past the limit (approximately 10KB) We do not return detailed feedback for tests that run after the 10KB limit is reached. For this project, you may submit your code as many times as you wish for the Warmup exercises. For Parts 1 & 2 (each of which consists of a client and a server part) you will have a limit of no more than 50 submissions between now and the final due date; you may use them all within one day, or you may use one per day - the choice is yours. We strongly encourage you to think about testing your own code. Test driven development is a standard technique for software, including systems software. The auto-grader is a grader and not a test suite. Note: your project readme file (10% of your grade for Project 1) is submitted on Canvas in PDF format. The project readme file is limited to 12 pages. Please keep your project readme as short as possible while still covering the requirements of the assignment. We do not use the "activate" feature Gradescope includes an "activate" feature that purportedly tells you which version of your code you want us to grade; we do not use this feature. We always grade your last submission prior to the deadline. This is due to the nature of our assignments, which can have race conditions; allowing you to run the same code 10 times and pick the one that worked is antithetical to our learning objectives. Thus, we use your last submission. Plan accordingly. README Throughout the project, we encourage you to keep notes on what you have done, how you have approached each part of the project and what resources you used in preparing your work. We have provided you with a prototype file, readme-student-template.md that you may use as the basis for this report. You are not required to use this format. Warm-up: Sockets In this project, your client and server will communicate via sockets. To help you familiarize yourself with C’s standard socket API, you will complete a few warm-up exercises Echo Client-Server Most socket tutorials start with a client-server pair where the server simply echoes (that is, repeats back) the message that the client sends. Sometimes referred to as the EchoClient and the EchoServer. In the first part of this assignment, you will turn in a pair of programs that perform these roles. For this first part of the assignment, we will make some simplifying assumptions. You may assume that neither the message to the server nor the response will be longer than 15 bytes. Thus, you may statically allocate memory (e.g. char buffer[16];) and then pass this memory address into send or recv. Because these messages are so short, you may assume that the full message is sent or received in every send or recv call. (If you may like, you may detect when this is not the case by looking at the return value and simply exiting if the full message is not sent or received). Neither your server nor your client should assume that the string response will be null-terminated, however. It is important that the only output (either to stdout or stderr) be the response from the server. Any missing or additional output causes the test to fail. Your echoserver should not terminate after sending its first response; rather, it should prepare to serve another request. You may consult the references suggested in this document or others on the internet. Your programs should support both IPv4 and IPv6. We have tests in subsequent parts to test support for IPv4 and IPv6. Once you have completed your programs inside the echo directory, you upload it to Gradescope (which you can find from Canvas). Once submitted, Gradescope will test your echoclient.c code with its own reference implementation of echoserver.c and your echoserver.c code with its own reference implementation of echoclient.c. It will then return some feedback to help you refine your code if it does not meet requirements. Note For this part of the assignment, you may submit your code as many times as you would like. Your grade is based upon the grade of your last submission. Transferring a File In this part of the assignment, you will implement code to transfer files on a server to clients. The basic mechanism is simple: when the client connects to the server, the server opens a pre-defined file (from the command line arguments), reads the contents from the file and writes them to the client via the socket (connection). When the server is done sending the file contents, the server closes the connection. Because the network interface is a shared resource, the OS does not guarantee that calls to send will copy the contents of the full range of memory that is specified to the socket. Instead, (for non-blocking sockets) the OS may copy as much of the memory range as it can fit in the network buffer and then lets the caller know how much it copied via the return value. int socket; char *buffer size_t length; ssize_t sent; /* Preparing message */ … /*Sending message */ sent = send(socket, buffer, length, 0); assert( sent == length); //WRONG! You should not assume that sent has the same value as length. The function send may need to be called again (with different parameters) to ensure that the full message is sent. Similarly, for recv, for TCP sockets, the OS does not wait for the range of memory specified to be completely filled with data from the network before the call returns. Instead, only a portion of the originally sent data may be delivered from the network to the memory address specified in a recv operation. The OS will let the caller know how much data it wrote via the return value of the recv call. In several ways, this behavior is desirable, not only from the perspective of the operating system which must ensure that resources are properly shared, but also from the user’s perspective. For instance, the user may have no need to store in memory all of the data to be transferred. If the goal is to simply save data received over the network to disk, then this can be done a chunk at a time without having to store the whole file in memory. In fact, it is this strategy that you should employ as the second part of the warm-up. You are to create a client, which simply connects to a server--no message need be sent-- and saves the received data to a file on disk. Beware of file permissions. Make sure to give yourself read and write access, e.g. S_IRUSR | S_IWUSR as the last parameter to open. A sender of data may also want to use this approach of sending it a chunk at a time to conserve memory. Employ this strategy as you create a server that simply begins transferring data from a file over the network once it establishes a connection and closes the socket when finished. Your server should not stop after a single transfer, but should continue accepting and transferring files to other clients. Your client should terminate after receiving the full contents. Unlike a normal web server (which leaves the socket open until the client closes it) your server should close the socket so the client knows when the full contents of the file have been transmitted. Note that the length of the file being sent is otherwise not known to the client; adding it to your client and server means it will not pass the grader because it does not implement the same protocol. You may consult the references suggested in this document or others on the internet. Starter code is provided inside of the transfer directory. Once you have completed your programs inside this directory, you may upload it to Gradescope. Part 1: Implementing the Getfile Protocol Getfile is a simple (HTTP-like) protocol used to transfer a file from one computer to another that we made up for this project. A typical successful transfer is illustrated below. The general form of a request is Note: The scheme is always GETFILE. The method is always GET. The path must always start with a ‘/’. The general form of a response is Note: The scheme is always GETFILE. The status must be in the set {‘OK’, ‘FILE_NOT_FOUND’, ‘ERROR’, 'INVALID'}. INVALID is the appropriate status when the header is invalid. This includes a malformed header as well an incomplete header due to communication issues. FILE_NOT_FOUND is the appropriate response whenever the client has made an error in his request. ERROR is reserved for when the server is responsible for something bad happening. No content may be sent if the status is FILE_NOT_FOUND or ERROR. When the status is OK, the length should be a number expressed in ASCII (what sprintf will give you). The length parameter should be omitted for statuses of FILE_NOT_FOUND, INVALID, or ERROR. The character '\r' is a single byte, which when used in a C literal string is translated by the compiler to be a carriage return. The character '\n' is a single byte, which when used in a C literal string is translated by the compiler to be a newline character. The sequence ‘\r\n\r\n’ marks the end of the header. All remaining bytes are the files contents. This is four bytes of data. The space between the and the and the space between the and the are required. There should not be a space between the and '\r\n\r\n'. The space between the and the and the space between the and the are required. There should not be a space betwen the and '\r\n\r\n'. There should not be a space between and '\r\n\r\n'. The length may be up to a 64 bit decimal unsigned value (that is, the value will be less than 18446744073709551616) though we do not require that you support this amount (nor will we test against a 16EB-1 byte file). Note the strings are not terminated with a null character. The buffers that you receive are not C strings. Just like HTTP, this is a language neutral format. Do not assume that anything you receive is null ('\0') terminated. You should avoid using string functions unless you have ensured that the data has been null-terminated. Instructions For Part 1 of the assignment you will implement a Getfile client library and a Getfile server library. The API and the descriptions of the individual functions can be found in the gfclient.h and gfserver.h header files. Your task is to implement these interfaces in the gfclient.c and gfserver.c files respectively. To help illustrate how the API is intended to be used and to help you test your code we have provided the other files necessary to build a simple Getfile server and workload generating client inside of the gflib directory. It contains the files Makefile - (do not modify) used for compiling the project components content.[ch] - (do not modify) a library that abstracts away the task of fetching content from disk. content.txt - (modify to help test) a data file for the content library gfclient.c - (modify and submit) implementation of the gfclient interface. gfclient.h - (do not modify) header file for the gfclient library gfclient-student.h - (modify and submit) header file for students to modify - submitted for client only gfclient_download.c - (modify to help test) the main file for the client workload generator. Illustrates use of gfclient library. gfserver.c - (modify and submit) implementation of the gfserver interface. gfserver.h - (do not modify) header file for the gfserver library. gfserver-student.h - (modify and submit) header file for students to modify - submitted for server only gfserver_main.c (modify to help test) the main file for the Getfile server. Illustrates the use of the gfserver library. gf-student.h (modify and submit) header file for students to modify - submitted for both client and server gf-student.c (modify and submit) implementation file for students to modify - submitted for both client and server handler.o - contains an implementation of the handler callback that is registered with the gfserver library. workload.[ch] - (do not modify) a library used by workload generator workload.txt - (modify to help test) a data file indicating what paths should be requested and where the results should be stored. gfclient The client-side interface documented in gfclient.h is inspired by libcurl’s “easy” interface. To help illustrate how the API is intended to be used and to help you test your code, we have provided the file gfclient_download.c. For those not familiar with function pointers in C and callbacks, the interface can be confusing. The key idea is that before the user tells the gfclient library to perform a request, user should register one function to be called on the header (gfc_set_headerfunc) and register one function to be called for every “chunk” of the body (gfc_set_writefunc). That is, one call to the latter function will be made for every recv() call made by the gfclient library. (It so happens that none of the test code actually will use the header function, but please implement your library to support it anyway.) The user of the gfclient library may want the callback functions to have access to data besides the information about the request provided by the gfclient library. For example, the write callback may need to know the file to which it should write the data. Thus, the user can register an argument that should be passed to the callback on every call. She or he does this with the gfc_set_headerarg and gfc_set_writearg functions. (Note that the user may have multiple requests being performed at once so a global variable is not suitable here.) Note that the gfcrequest_t is used as an opaque pointer, meaning that it should be defined within the gfclient.c file and no user code (e.g. gfclient_download.c) should ever do anything with the object besides pass it to functions in the gfclient library. gfserver The server side interface documented in gfserver.h is inspired by python’s built-in httpserver. The existing code in the file gfserver_main.c illustrates this usage. Again, for those not familiar with function pointers in C and callbacks, the interface can be confusing. The key idea is before starting up the server, the user registers a handler callback with gfserver library which controls how the request will be handled. The handler callback should not contain any of the socket-level code. Instead, it should use the gfs_sendheader, gfs_send, and potentially the gfs_abort functions provided by the gfserver library. Naturally, the gfserver library needs to know which request the handler is working on. All of this information is captured in the opaque pointer passed into the handler, which the handler must then pass back to the gfserver library when making these calls. Submission You should submit your code via Gradescope. Part 2: Implementing a Multithreaded Getfile Server Note: For both the client and the server, your code should follow a boss-worker thread pattern. This will be graded. Also keep in mind this is a multi-threading exercise. You are NOT supposed to use fork() to spawn child processes, but instead you should be using the pthreads library to create/manage threads. You will have points removed if you don't follow this instruction. In Part 1, the Getfile server can only handle a single request at a time. To overcome this limitation, you will make your Getfile server multi-threaded by implementing your own version of the handler in handler.c and updating gfserver_main.c as needed. The main, i.e. boss, thread will continue listening to the socket and accepting new connection requests. New connections will, however, be fully handled by worker threads. The pool of worker threads should be initialized to the number of threads specified as a command line argument. You may need to add additional initialization or worker functions in handler.c. Use extern keyword to make functions from handler.c available to gfserver_main.c. For instance, the main file will need a way to set the number of threads. Similarly on the client side, the Getfile workload generator can only download a single file at a time. In general for clients, when server latencies are large, this is a major disadvantage. You will make your client multithreaded by modifying gfclient_download.c. This will also make testing your getfile server easier. In the client, a pool of worker threads should be initialized based on number of client worker threads specified with a command line argument. Once the worker threads have been started, the boss should enqueue the specified number of requests (from the command line argument) to them. They should continue to run. Once the boss confirms all requests have been completed, it should terminate the worker threads and exit. We will be looking for your code to use a work queue (from steque.[ch]), at least one mutex (pthread_mutex_t), and at least one condition variable (pthread_cond_t) to coordinate these activities. Gradescope will confirm that your implementation meets these requirements. The folder mtgf includes both source and object files. The object files gfclient.o and gfserver.o may be used in-place of your own implementations. Source code is not provided because these files implement the protocol for Part 1. Note: these are the binary files used by Gradescope. They are known not to work on Ubuntu versions other than 20.04. They are 64 bit binaries (only). If you are working on other platforms, you should be able to use your protocol implementation files from Part 1. Makefile - (do not modify) used for compiling the project components content.[ch] - (do not modify) a library that abstracts away the task of fetching content from disk. content.txt - (modify to help test) a data file for the content library gfclient.o - (do not modify) implementation of the gfclient interface. gfclient.h - (do not modify) header file for the gfclient library gfclient-student.h - (modify and submit) header file for students to modify - submitted for client only gfclient_download.c - (modify and submit) the main file for the client workload generator. Illustrates use of gfclient library. gfserver.o - (do not modify) implementation of the gfserver interface. gfserver.h - (do not modify) header file for the gfserver library. gfserver-student.h - (modify and submit) header file for students to modify - submitted for server only gfserver_main.c (modify and submit) the main file for the Getfile server. Illustrates the use of the gfserver library. gf-student.h (modify and submit) header file for students to modify - submitted for both client and server gf-student.c (modify and submit) implementation file for students to modify - submitted for both client and server handler.c - (modify and submit) contains an implementation of the handler callback that is registered with the gfserver library. steque.[ch] - (do not modify) a library you must use for implementing your boss/worker queue. workload.[ch] - (do not modify) a library used by workload generator workload.txt - (modify to help test) a data file indicating what paths should be requested and where the results should be stored. Grading Your code should be submitted via Gradescope. Readme Throughout your development you should be keeping notes about what you are doing for your development. We encourage you to work on your your readme file as your project develops, so that it can serve as a log of your work. To obtain all possible points, we want you to demonstrate your understanding of what you have done. We are not looking for a diary, we are looking for a clear explanation of what you did and why you did it. This is your grader's opportunity to award you points for understanding the project, even if you struggle with the implementation, as these are manually graded. NOTE: This is your opportunity to clearly document your reference materials. Finally, we encourage you to make concrete suggestions on how you would improve this project. This is not required for the project, but is an opportunity for you to earn extra credit points. This could also include sample code, suggested tests (we really like examples!), ways to improve the documentation, etc. You must submit: A file named yourgtaccount-analysis.pdf containing your writeup (GT account is what you log in with, not your all-digits ID. Example: jdoe1-analysis.pdf). This file will be submitted via Canvas as a PDF (Project 1 README assignment). You may use any tool you desire to create it, so long as it is a compliant PDF - and for us. Compliant means "we can open it using Acrobat Reader". The project readme is limited to 12 pages. Please keep your readme as short as possible while still covering all requirements of the assignment. Points will be deducted if the project readme exceeds the page limit. NOTE: Some of the best readme files submitted are not long, but short, clear, and concise, including all requirements. This approach is particularly effective for a Georgia Tech graduate-level class, where clarity and conciseness are highly valued. References Sample Source Code Server and Client Example Code - note the link referenced from the readme does not work, but the sample code is valid. Another Tutorial with Source Code for server and client General References POSIX Threads (PThreads) Linux Sockets Tutorial Practical TCP/IP Sockets in C Guide to Network Programming Helpful Hints High-level code design of multi-threaded GetFile server and client Return code (exit status) 11 of client or server means it received a SIGSEGV (segmentation fault). You can get a comprehensive list of signals with kill -l. In the warm-up part, the server should be running forever. It should not terminate after serving one request. Use the class VM to test and debug your code. The autograder is not a test harness. Rubric Warm-up (20 points) Echo Client-Server (10 points) Transfer (10 points) Your submission should compile and build without any errors on gradescope. For echo client-server: Your client program will be tested to make sure it correctly prints the message that was received from the server and your server will be tested to make sure it correctly echoes the message sent by the client. Note your submission may fail tests if it prints or echoes any additional characters (including formatting options such as newline characters.) For transfer: Your client should successfully save the file sent from the sever on the disk and the server should accurately send the file to the client. File size and contents on the client should match the file size and contents on the server side. Part 1: Getfile Libraries (30 points) Client (15 points) Server(15 points) Full credit requires: code compiles successfully, does not crash, files fully transmitted, basic safety checks (file present, end of file, etc.), and proper use of sockets - including the ability to restart your server implementation using the same port. Note that the automated tests will test some of these automatically, but graders may execute additional tests of these requirements. Our tests include malformed requests such as invalid scheme (eg: PULLFILE), invalid method (eg: FETCH) and invalid path (eg: foo); requests for files that are not on the server as well as scenarios where the server is unable to process the client request. Likewise, our tests include valid requests that may result in a single message from the server (ie a single message with both the response header and data in the same message) or multiple messages from the server (response header or data sent in multiple messages, message size may or may not vary). In addition to the above tests , we also run some sanity tests to ensure your submission compiles & builds without any errors on gradescope and proper initialization & cleanup is performed (eg: no memory leaks and no invalid memory accesses). Part 2: Multithreading (40 points) Client (20 points) Server(20 points) Full credit requires: code compiles successfully, does not crash, does not deadlock, number of threads can be varied, concurrent execution of threads, files fully transmitted, correct use of locks to access shared state, no race conditions, etc. Note that the automated tests will test some of these automatically, but graders may execute additional tests of these requirements. In addition to the sanity tests discussed in part 1, our tests will validate if your submission supports multiple file downloads of varying file sizes concurrently. Your implementation employs boss worker model to distribute work and uses appropriate synchronization mechanisms to protect shared data. README (10 points + 5 point extra credit opportunity) Clearly demonstrates your understanding of what you did and why - we want to see your design and your explanation of the choices that you made and why you made those choices. (5 points) A description of the flow of control for your code; we strongly suggest that you use graphics here, but a thorough textual explanation is sufficient. (2 points) A brief explanation of how you tested your code. (2 points) References any external materials that you consulted during your development process (1 point) Suggestions on how you would improve the documentation, sample code, testing, or other aspects of the project (up to 5 points extra credit available for noteworthy suggestions here, e.g., actual descriptions of how you would change things, sample code, code for tests, etc.) We do not give extra credit for simply reporting an issue - we're looking for actionable suggestions on how to improve things. Partial Credit - some tests are run multiple times and credit is awarded for successul runs. This is the only partial credit we award. If your code did not work but you can explain why fully in your README file, we may give you full marks in the README. In cases where we identify an issue with the grader that impacts your project, we may manually adjust the final scores. For example, if we find that your code fails to implement required functionality but the grader failed to detect this, we may reduce the score. Similarly, if we find an issue with the grader that failed to credit you properly, we may adjust the score manually. Normally this is done by running a modified version of the grader that is corrected. This is unusual, but has happened in the past.. Ideal README - the ideal README file is one that you could have picked up at the start of the project and used it to guide your development. It would explain the choices you considered and why you chose specific approaches to the problem. It won't complain about the code, the process, how little you know about C, or other things unrelated to the project. It won't discuss the code; it will discuss the techniques and algorithms. Thus, a README file that explains the issues you faced, or provides an English description of your code, will receive at most half-points. A README file that explains what choices you faced, why you chose to implement it how you did, how you implemented it, and what your conclusions are about that choice can be awarded up to full marks. Questions For all questions, please use the class Piazza forum or Slack Workspace so that TAs and other students can assist you.
1 Assignment ObjecOve The goal of this assignment is to gain experience with both TCP and UDP socket programming in a client-server environment (Figure 1). You will use Python or any other programming language to design and implement a client program (client) and a server program (server) to communicate between themselves.2 Assignment SpecificaOons 2.1 Summary In this assignment, the client will send requests to the server to reverse strings (taken as a command line input) over the network using sockets. This assignment uses a two-stage communicaOon process. In the negoOaOon stage, the client and the server negoOate on a random port () for later use through a fixed negoOaOon port () of the server. Later in the transacOon stage, the client connects to the server through the selected random port for actual data transfer. 2.2 Signaling The signaling in this project is done in two stages as shown in Figure 2. Stage 1. Nego+a+on using TCP sockets: In this stage, the client creates a TCP connecOon with the server using as the server address and as the negoOaOon port on the server (where the server is listening). The client sends a request to get the random port number from the server where it will send the actual request (i.e., the string to be reversed). To iniOate this negoOaOon, the client sends a request code (), an integer (e.g., 13), a]er creaOng the TCP connecOon. If the client fails to send the intended , the server closes the TCP connecOon and conOnues listening on for subsequent client requests. Once the server verifies the , it replies back with a random port number where it will be listening for the actual request. A]er receiving this , the client closes the TCP connecOon with the server.Stage 2. Transac+on using UDP sockets: In this stage, the client creates a UDP socket to the server in and sends the containing a string. On the other side, the server receives the string and sends the reversed string back to the client. Once received, the client prints out the reversed string and exits. Note that the server should conOnue listening on its for subsequent client requests. For simplicity, we assume, there will be only one client in the system at a Ome. So, the server does not need to handle simultaneous client connecOons. 2.3 Client Program (client) You should implement a client program, named client. It will take four command line inputs: , , , and in the given order. 2.4 Server Program (server) You should also implement a server program, named server. The server will take as a command line parameter. The server must print out the value in the following format as the first line in the stdout: SERVER_PORT= For example, if the negoOaOon port of the server is 52500, then the server should print: SERVER_PORT=52500 2.5 Example ExecuOon Two shell scripts named server.sh and client.sh are provided. Modify them according to your choice of programming language. You should execute these shell scripts which will then call your client and server programs. • Run server: ./server.sh • Run client: ./client.sh ‘A man, a plan, a canal— Panama!’ 3 Hints Below are some points to remember while coding/debugging to avoid trivial problems. • You can use and adapt the sample codes of TCP/UDP socket programming in Python slides (last few slides Chapter 2). • Use port id greater than 1024, since ports 0-1023 are already reserved for different purposes (e.g., HTTP @ 80, SMTP @ 25) • If there are problems establishing connecOons, check whether any of the computers running the server and the client is behind a firewall or not. If yes, allow your programs to communicate by configuring your firewall so]ware. • Make sure that the server is running before you run the client. • Also remember to print the where the server will be listening and make sure that the client is trying to connect to that same port for negoOaOon. • If both the server and the client are running in the same system, 127.0.0.1 or localhost can be used as the desOnaOon host address. • You can use help on network programming from any book or from the Internet, if you properly refer to the source in your programs. But remember, you cannot share your program or work with any other student. 4 Procedures 4.2 Hand in InstrucOons Submit all your files in a single compressed file (.zip, .tar etc.) using LEARN in dedicated Dropbox. The filename should include your username and/or student ID. You must hand in the following files / documents: • Source code files. • Makefile: your code must compile and link cleanly by typing “make” or “gmake” (when applicable). • README file: this file must contain instrucOons on how to run your program, which undergrad machines your program was built and tested on, and what version of make and compilers you are using. • Modified server.sh and client.sh scripts. Your implementaOon will be tested on the machines available in the undergrad environment linux.student.cs which includes the following hosts:4.3 DocumentaOon 4.4 EvaluaOon Work on this assignment is to be completed individually. 5 AddiOonal Notes: • You have to ensure that both and are available. Just selecOng a random port does not ensure that the port is not being used by another program. • All codes must be tested in the linux.student.cs environment prior to submission. • Run client and server in two different student.cs machines • Run both client and server in a single student.cs machine • Make sure that no addiOonal (manual) input is required to run any of the server or client.
PROBLEM You will be given a training dataset which consists of bus data for 4 types of existing bus trips, namely square, circle, star, real_world. Click here to download dataset (Refer to dataset_README.md) Dataset for each of the above types of trips, is present in a csv file consisting of several attributes. Naming format is _.csv, which is self explanatory. What you need to submit is mentioned in the next slide. A SUBMISSION For each of the 5 test csv files namely, square_test, circle_test, star_test, real_1_test, real_2_test, follow steps 2-6. Steps 2-6 are illustrated for the square type in particular. For the provided square_test.csv containing 50 data points, your task is to predict the next 25 bus locations, based on the 50 data points. Put these 25 predictions in a csv file named _square.csv. Now use the combined data (50 provided by us initially + 25 data points generated in step 1). Take the last 50 rows of this new dataset and predict the next 25 locations based on these. Append these 25 predictions to _square.csv. Now you will have totally (50 [initial] + 25 [from step 2] + 25 [from step 3] = 100) data points. Now again use this data consisting of 100 data points, take the last 50 rows from this and predict the next 25 locations. Append these 25 predictions to _square.csv. Repeat steps 2-5 in a cyclic manner until you generate 250 data points (excluding the initial 50 we provided you). (There must be 250 rows in _square.csv.)Contact Us Agrim Jain +91 9528876421 [email protected] Shashank P +91 9483303320 [email protected]
The specifications in this document are subject to minor changes if further clarification is needed 1. Problem Description Battery-Electric and Hybrid-Electric vehicles are becoming more and more economical, efficient and environmentally friendly resulting in an increase in adoption rates. In addition, the recent advancements in autonomous electric vehicles are also resulting in the automotive industry starting to transition from petrol to electric vehicle design. As an embedded system engineer you have been contracted by an automotive manufacture who is transitioning from petrol to Battery-Electric technology. Your task is to design the real time sensing, motor control and user interface for the electric vehicle. Your goal is to develop the embedded software to safely control and monitor an electric vehicle including the sensing and actuation of a 3-phase Brushless DC (BLDC) motor commonly used in electric vehicles. This will include monitoring the state of the motor such as velocity, power and temperature and handle the start-up, braking and emergency procedures for the system. Your system design will require real-time handling of multiple tasks for sensor acquisition and filtering, motor fault handling and system display of critical information. Your setup includes a motor testing station including the motor driver and sensor board and a development kit for the Tiva TM4C1294NCPDT microcontroller. Figure 1b illustrates the setup interface of the testing station. Inputs and outputs of sensors and per-phase connections are compatible with the requirements of the microcontroller ports, with an electrical interface to achieve this. The mapping of the microcontroller pins (GPIO, I2C, ADC, UART) and the motor driver inputs and outputs is provided in a separate document. Additional resources that will be provided for this assignment includes a description of the operation of the motor, a custom motor driver library (MotorLib) and a motor kit setup guide.(a) (b)(c) Figure 1: (a) Simulated Electric Vehicle Sensor and Motor Testing Station. The system includes a microcontroller development kit, a motor driver and sensor board, brushless motor with hall effect sensors for position and velocity feedback and temperature and current sensors for fault monitoring. (b) BOOSTXL-DRV8323RH Motor Control Launchpad Boosterpack. (c) a simplified block diagram of the hardware used within this assignment. Please see the additional assignment reference document for a more detailed pinout of the Boosterpack headers 2. Requirements The assignment can be separated into three main sections: Motor Control, Sensing and User Interface. Each section has different requirements and are described below. You are required to design the solution using a software driver model for each subsystem. The final software will then use the driver functionalities to integrate each subsystem into one coherent solution for demonstration. Your team should coordinate and design the software system together in order to manage events, shared resources and CPU utilisation, taking into account the priority of each subsystem and their tasks. 2.1 Motor Control You are to write a device driver for the DRV832x motor driver board (including the additional custom motor adapter board) to provide an Application Programming Interface (API) that will: 1. Start and control the motor safely, handling any fault conditions using the provided state transition diagram (see supporting documents for how to control the phases of the motor) 2. Control a user given desired speed of the motor in revs/min 3. Safely start and accelerate the motor to the desired speed (See below for acceleration specifications) 4. Safely decelerate the motor (See below for deceleration specifications) The acceleration and deceleration limits are defined as: 1. Motor Acceleration ≤ 500RPM/s 2. Motor Deceleration (setting slower speed) ≤ 500RPM/s 3. Motor Deceleration (emergency stop aka e-stop) = 1000RPM/s Please ensure you handle units correctly as acceleration and deceleration values will be tested. Note, the deceleration for e-stop should be equal to (not greater or less than) the desired value as we would like the vehicle to come to a complete stop quickly but safely. 2.1.1 E-stop Conditions The following conditions should cause the motor control to enter into an e-stop condition causing the motor to safely brake using the previously indicated deceleration limit. For the temperature, acceleration and heading conditions, only implement the condition if you have selected the sensor in section 2.3. 1. Total motor current has exceeded a user defined threshold 2. Temperature has exceeded a user defined threshold 3. Absolute acceleration has exceeded a user defined threshold (an impact has occurred) measured via the accelerometer sensor (see section 2.3) 4. Heading of vehicle has exceeded a user defined upper and lower threshold (the car is sideways) measured via the compass sensor (see section 2.3) 5. Distance has gone below a user defined threshold (vehicle is about to hit an obstacle) measured via the Time of Flight distance sensor (see section 2.3) 2.2 Motor Library and Motor Kits A custom motor library will be supplied to your group in order for you to easily and safely commutate (switch) the phases of the motor. This will be available via Blackboard and separate instructions will be supplied describing how to install and use the library. You must use this motor library to minimise the risk of damaging the motor kits supplied with this assignment. However, this does not guarantee that the motors will not be damaged and it is recommended that the motor kits are monitored during operation and if debugging your software while operating the motors that either the motor kits are powered down or monitored such that the do not heat up significantly. The teaching team have added some protection mechanisms (motor adapter board and current limited power supplies) to minimise this risk but with all electrical and mechanical hardware it is almost impossible to protect against all possible failures. 2.3 Sensing In order to monitor critical information on the state of the vehicle you will need to write a device driver for the various sensors available on the vehicle. You will need to write the sensor drivers in order to provide an Application Programming Interface (API) to perform the following functionalities: 1. Power Sensing – Read and filter two motor phase currents via the analogue signals provided by the current sensors on the DRV8323 board (only two sense lines are available as ADC inputs to the microcontroller). Using the motor current and motor voltage (24V nomimal) calculate the power usage of the motor. 2. Speed Sensing – Measure and filter the current speed of the motor in revs/min (rpm) Choose 2 out of the 5 following sensors to add to your project: 1. Vechicle acceleration (BMI160) – Read and Filter the acceleration on all three axis and calculate average absolute acceleration (sum of absolute acceleration in each axis). This can be used to detect a sudden crash. 2. Temperature (OTP-538U) – Read and filter the temperature from the temperature sensor over via a I2C connection provided by the QUT sensor breakout board. 3. Compass (BMM150) – Read and filter the magnetometer on all three axis and calculate the heading of the vehicle from the x and y axis. 4. Light Level – Read and filter the light level from the OPT3001 ambient light sensor over an I2C connection. 5. Distance (VL53L0X) – Read and filter the Time of Flight (ToF) distance sensor over an I2C connection. 2.3.1 Data Filtering Sensor data usually suffer from measurement noise. In order to correctly identify faults in a real-time fashion and ensure noise does not trigger false alarms you must filter this data before displaying it. You must filter the data using the following specifications: • Current (DRV8323) – sample buffer size of 5 or more, sampled at a rate ≥ 150 Hz • Speed (Hall Sensors) – sample buffer size of 5 or more sampled at a rate ≥ 100 Hz • Accelerometer (BMI160) – sample buffer size (of each axis) of 5 or more sampled at a rate ≥ 200 Hz • Temperature (OTP-538U) – sample buffer size of 3 or more sampled at a rate ≥ 1 Hz. • Compass (BMM150) – sample buffer size (of each axis) of 3 or more sampled at a rate ≥ 10 Hz • Light (OPT3001) – sample buffer size greater than 5 sampled at a rate ≥ 2 Hz • Distance (VL53L0X) – sample buffer size greater than 5 sampled at a rate ≥ 5 Hz 2.4 User Interface You are required to develop a graphical user interface to control the operation of the electric vehicle and display the state of the vehicle. This includes displaying critical information and including the ability to change the status of the vehicle. You should consider the layout of the interface for easy control and display of the information. A list of specific features of the user interface is defined below: 1. Starting and stopping the motor using buttons (on-screen or push button) 2. Displaying start and stopped status using an LED 3. Setting the desired speed of the motor using user input A feature of the user interface is the ability to set upper and lower limits which then throw an e-stop condition if outside these limits. The following limits should be implemented and have the ability to be modified via the user interface. 1. Setting an upper limit of allowable current drawn by the motor. If this condition is met a fault has occurred, an e-stop condition should be flagged and the motor should be stopped safely Implement the following sensor specific features depending on which 2 sensors you selected out of the 4 given from section 2.3: 1. Light – Classify and display whether it is currently day or night (night time is classified as the ambient light being less than 5 lux). Turn on an LED when the time of day is classified as night time (simulating auto headlights). 2. Temperature – Setting an upper limit of allowable temperature of the motor. If this condition is met a fault has occurred and the motor should be stopped safely 3. Acceleration – Set up an upper limit of allowable acceleration of the vehicle. If this condition is met a fault has occurred, an e-stop condition should be flagged and the motor should be stopped safely. 4. Compass – Set up an upper and lower limit of allowable heading of the vehicle. If this condition is met a fault has occurred, an e-stop condition should be flagged and the motor should be stopped safely. 5. Distance – Set up a lower limit of allowable distance to an obstacle in front of the vehicle. If this condition is met a crash is about to occur and an e-stop condition should be flagged and the motor should be stopped safely. On a second page/tab within the user interface you will be required to plot the filtered sensor information from the vehicle in a real-time, user friendly manner. Use your own design/structure for displaying the sensor information, but it must display the following information as a moving plot over time: 1. motor speed (rpm) 2. approximate power usage of the motor using the phase current measurements (in watts) Only display the following 2 sensors that were chosen to be implemented from section 2.3 1. Light – ambient light level (in Lux) 2. Temperature – current temperature (in Degrees Celsius) 3. Acceleration – Average absolute acceleration from the accelerometer (m/s2) 4. Compass – Heading of the vehicle (in degrees) 5. Distance – Distance to any object in front of the vehicle (in metres) For displaying the sensor data, units can be of different magnitudes (e.g. Kilowatts), scaled or adjusted for display purposes. 3. Demonstration You are required to present and demonstrate your work to the teaching team. The groups will present as a team; however, you will be individually assessed. For the demonstration, you should prepare to show and talk about what you have done. You will also be asked questions throughout your demonstration. Additional advanced features will also improve your mark only if the design requirements for that system have been met. For the presentation you should aim to present your designed system to the client which is the automotive manufacturing company (teaching team). Your presentation should include an overall description of your final design, how you have met specifications and showing all relevant details. The duration is strictly 3 minutes per student for presentation (come prepared for this) and 13 minutes for demonstration. You should prepare only one PowerPoint slide per student. 4. Assessment 4.1 Mark Distribution Presentation (5%) – Based on effectiveness of communication, use of visuals and quality of the presentation by each student. Achievement (15%) – Based on demonstration of evidence that requirements are met. Report (10%) – A suggested report format is provided at the end of this document. Criterion Referenced Assessment Sheet – CRA sheets for the demonstration and report will be available on Blackboard 4.2 Late Demonstration This will not be permitted except for cases permitted by QUT policy. Regardless of the state of completion of your assignment work, you are required to make a presentation as scheduled describing your work up to that time. 4.4 Requirements that could not be demonstrated You can add an explanation for each failure if you have been able to figure out how you might proceed if you could do it again. 5. Suggested Format of the Report The report should contain the following items. The content and style are flexible if these are separately identifiable. Approximate page guidelines are given in parentheses. • Cover page – names, student ID numbers, course, and unit information. (1 page) • Table of Contents – Section headings, list of figures, list of tables. (1 to 2 pages) • Introduction – Problem statement, context, requirements, and statements on the individual contributions by each team member. (2 pages) • Design and Implementation – Approach to design, important issues and choices and their relationships to theoretical concepts and the hardware and software platforms. Check if you have addressed: – Provided a graphical representation for your design? – Provided a Project Folders and Files diagram? – Did you use the GPIO module? How? Did you use the graphics library? How? Did you use Tasks, Hwi and Swi? How? – Did you use multiple threads/handlers? How? Did you use the ADC? How? • Results – Summary of evidence of functional requirements that were demonstrated and explanation of failures as learning outcomes in terms of what could have been done differently. (2 pages) • References – Including vendor supplied technical documents with a table that links each document to sub-sections of your report where they are relevant with entries: The reference number, the sub-section number, topic keyword or keywords, the pages that were found useful. (2 pages) • Appendix – Mention the name of the hardware development platform and versions of the tools used such as Code Composer Studio, Tivaware, TI-RTOS, etc. (1 page) Reference Documents • DRV832x 6 to 60-V Three-Phase Smart Gate Driver Datasheet • DRV832XX EVM Sensored Software User’s Guide • BOOSTXL-DRV8323Rx EVM User’s Guide • TI-RTOS User’s Guide • TI-RTOS SYS/BIOS User’s Guide • EK-TM4C1294XL User’s Guide • TM4C1294NCPDT Datasheet • OPT3001 Ambient Light Sensor Datasheet • BOOSTXL-SENSORS Sensors BoosterPack User’s Guide • Grove IR Temperature Sensor – OTP-538U • Grove Time of Flight Distance Sensor – VL53LOX
1 Introduction In this assignment, you are to implement Dijkstra’s algorithm for single-source shortest-paths to find shortest paths to different users from a given user. A user’s data is stored in struct record. The location of the user is also stored in struct record. A user can have multiple friends. All the friends of a given user U are reachable from U. All the users that are reachable from the friends of U are also reachable from U. In this assignment, for a given user, U, you need to calculate the shortest distances and shortest paths to all other users that are reachable from U. 2 Type of record The type of a user’s record is given below. struct record { /* character string terminated with ’’ * maximum length is 16 */ char name[MAX_LEN]; /* a character array of 16 characters * not-necessarily terminated with ’’ * anywhere in the character array */ char uid[MAX_LEN]; int age; /* used for verification */ int verify; /* location */ struct location loc; /* list of posts */ struct list_posts *posts; /* list of friends */ struct list_records *friends; /* needed for shortest Path */ int status; struct record *pred; double distance; /* needed for the tree data-structure */ int height; struct record *left; struct record *right; struct record *parent; }; The loc field of type struct location contains the location of the user. struct location contains two fields, lat and lon, that correspond to the latitude and longitude, respectively. You need to use the distance function to compute the distance between two users. The other fields that are relevant in this assignment are friends, status, pred, and distance. The friends field contains the head of the linked list that stores the references to the records corresponding to a user’s friends. The type of friends is struct list records, as shown below. struct list_records { struct record *record; struct list_records *next; }; A node of type struct list records stores a reference to struct record and the reference to the next node (using the next field). This can be used to implement the list of friends. You are not allowed to change existing structures (e.g., struct record, struct list records, etc.) in your implementation. The distance and pred fields contain the shortest distance and the predecessor on a shortest path computed by your algorithm. 3 Single-source Shortest-paths The struct record of a user U stores the references to other struct record nodes that correspond to the friends on U in a linked-list. The friends field in the struct record contains the head of this linked-list. If V is in the friends’ list of U, then U is also in the friends’ list of V. If two users are friends, they are connected via an undirected edge whose length is the distance between them. Two users are reachable from each other if a path exists between them. In this part, you need to compute a shortest path and the shortest distance to each user v that is reachable from a source user u. The shortest distance is the shortest distance between u and v. The shortest path is a shortest path between u and v. You need to implement Dijkstra’s algorithm for single-source shortest-paths. You can use a linear scan instead of a min-heap to find a vertex with the minimum distance in your implementation. For min-heap or linear scan implementation, you can use min heap arr. min heap arr is large enough to store all vertices in the graph. 4 Library interface In this assignment, you need to implement a library that implements all the functionalities we discussed above. The user interface for your library is given in the “pa4.h” file. Below is a short description of these interfaces. make friends(struct record *r1, struct record *r2): Make users r1 and r2 friends of each other if they aren’t already friends. The friends field in “struct record” stores the head of the linked-list that stores references to friends. To make r1 a friend of the r2, insert r1 in the linkedlist r2->friends and insert r2 in the linked-list r1->friends. Return 1 if r1 and r2 are already friends before this call. Return 0 if they become friends during this call. get friends list(struct record *r): Return the list of friends of r, i.e., r->friends. delete friends list(struct record *r): Remove all friends from r->friends and release the corresponding memory. 5 Compilation and running the test cases Clone the assignment repository using: git clone https://github.com/Systems-IIITD/DSALAB.git Implement everything in the “PA4/pa4.c” file. Don’t change any other files. Use printf to debug your code. Run “make” in the “PA4” folder to compile your library and the test case. There is only one test case. To run the test cases: use “./test1 10”. It will test your program for ten records. Once your implementation works for small sizes, test and debug it for large sizes. We will test your implementation for large input sizes. So make sure to test them for large inputs as well. You are not allowed to use malloc and free directly in your library. Use allocate memory and free memory routines provided to you instead of malloc and free. In this assignment, you are allowed to allocate memory only for the linked-list nodes in the list of friends. 5.1 How to submit echo “Compiling test-case 1” Compiling test-case 1 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test1 test1.c -ldsa -lpa4 -lm ./test1 1000 Creating 1000 uids took 0 ms. adding 1000 records took 0 ms. making 5982 friends took 0 ms. computing all shortest paths took 1608 ms. Test-case-1 passed ./test1 5000 Creating 5000 uids took 2 ms. adding 5000 records took 0 ms. making 29982 friends took 1 ms. computing all shortest paths took 86368 ms. Test-case-1 passed
1 Introduction 2 Type of record The type of a user’s record is given below. struct record { /* character string terminated with ’’ * maximum length is 16 */ char name[MAX_LEN]; /* a character array of 16 characters * not-necessarily terminated with ’’ * anywhere in the character array */ char uid[MAX_LEN]; int age; /* location */ struct location loc; /* list of posts */ struct list_posts *posts; /* list of friends */ struct list_records *friends; /* needed for shortest Path */ int status; struct record *pred; /* needed for the tree data-structure */ int height; struct record *left; struct record *right; struct record *parent; }; The uid field is the key used for the BST and the AVL tree. You can use left and right fields to store the references to left and right subtrees in an AVL or BST node. The height field is used for the AVL tree. The status field is used when a record is not present during search and delete operations. The friends field contains the head of the linked list that stores the references to the records corresponding to a user’s friends. The type of friends is struct list records, as shown below. struct list_records { struct record *record; struct list_records *next; }; A node of type struct list records stores a reference to struct record and the reference to the next node (using the next field). This can be used to implement the list of friends. You are not allowed to change struct record or struct list records in your implementation. 3 BST 4 AVL 5 Library interface In this assignment, you need to implement a library that implements all the functionalities we discussed above. The user interface for your library is given in the “pa2.h” file. Below is a short description of these interfaces. get bst root: Return the root of the BST, bst root. This implementation has already been provided. Please don’t change it. get avl root: Return the root of the AVL tree, avl root. This implementation has already been provided. Please don’t change it. insert record bst: Insert record r in the BST rooted at bst root. insert record avl: Insert record r in the AVL tree rooted at avl root. search record bst: Search the record corresponding to uid in the BST rooted at bst root. If the record is not present, return a dummy record with −1 in the status field; otherwise, return a copy of the record. search record avl: Search the record corresponding to uid in the AVL tree rooted at avl root. If the record is not present, return a dummy record with −1 in the status field; otherwise, return a copy of the record. make friends bst: Make users with uids uid1 and uid2 in the BST rooted at bst root friends of each other if they aren’t already friends. The friends field in “struct record” stores the head of the linked list of friends of a given user. To make the user with record A a friend of the user with record B, add A to B’s list of friends and add B to A’s list of friends. Return 1 if uid1 and uid2 are already friends before this call. Return 0 if they become friends during this call. make friends avl: Make users with uids uid1 and uid2 in the AVL tree rooted at avl root friends of each other if they aren’t already friends. The friends field in “struct record” stores the head of the linked list of friends of a given user. To make the user with record A a friend of the user with record B, add A to B’s list of friends and add B to A’s list of friends. Return 1 if uid1 and uid2 are already friends before this call. Return 0 if they become friends during this call. get friends list bst: The friends field in “struct record” stores the head of the linked list of friends of a given user. Return the head of the linked list of friends (i.e., the friends field) of the user with uid uid in the BST rooted at bst root. If the corresponding record doesn’t exist, return NULL. get friends list avl: The friends field in “struct record” stores the head of the linked list of friends of a given user. Return the head of the linked list of friends (i.e., the friends field) of the user with uid uid in the AVL tree rooted at avl root. If the corresponding record doesn’t exist, return NULL. delete record bst: Delete record (say n) corresponding to uid from the BST rooted at bst root. Also, remove n from the lists of friends of other records and release the memory for the linked list nodes. Release memory for all the nodes in the list of friends of n. Return a copy of the value of the deleted node. If the node is not present, return a dummy record with −1 in the status field. delete record avl: Delete record (say n) corresponding to uid from the AVL tree rooted at avl root. Also, remove n from the lists of friends of other records and release the memory for the linked list nodes. Release memory for all the nodes in the list of friends of n. Return a copy of the value of the deleted node. If the node is not present, return a dummy record with −1 in the status field. get num bst records: Return the total number of records in the BST rooted at bst root. get num avl records: Return the total number of records in the AVL tree rooted at avl root. destroy bst: Release memory for all BST nodes and their lists of friends. Make bst root points to an empty tree. destroy avl: Release memory for all AVL nodes and their lists of friends. Make avl root points to an empty tree. 6 Compilation and running the test cases Clone the assignment repository using: git clone https://github.com/Systems-IIITD/DSALAB.git Implement everything in the “PA2/pa2.c” file. Don’t change any other files. Use printf to debug your code. Run “make” in the “PA2” folder to compile your library and test cases. There are four test cases. To run the first test cases: use “./test1 10”. It will test your program for ten records. Once your implementation works for small sizes, test and debug it for large sizes. To run the second test for size 10, use “./test2 10”. To run the third test case for size 10, use “./test3 10”. To run the fourth test case for size 10, use “./test4 10”. We will test your implementation for large input sizes. So make sure to test them for large inputs as well. You are not allowed to use malloc and free directly in your library. Use allocate memory and free memory routines provided to you instead of malloc and free. 6.1 How to submit Sample report file. The output of make submit1: echo “Compiling test-case 1” Compiling test-case 1 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test1 test1.c -ldsa -lpa2 -lm ./test1 100000 Creating 100000 uids took 79 ms. adding 100000 records took 31 ms. making 599982 friends took 229 ms. search 100000 records took 25 ms. Test-case-1 passed ./test1 1000000 Creating 1000000 uids took 1548 ms. adding 1000000 records took 808 ms. making 5999982 friends took 6091 ms. search 1000000 records took 860 ms. Test-case-1 passed The output of make submit2: echo “Compiling test-case 2” Compiling test-case 2 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test2 test2.c -ldsa -lpa2 -lm ./test2 100000 Creating 100000 uids took 81 ms. adding 100000 records took 32 ms. making 599982 friends took 237 ms. deleting 50000 records took 465 ms. Test-case-2 passed ./test2 1000000 Creating 1000000 uids took 1562 ms. adding 1000000 records took 815 ms. making 5999982 friends took 6092 ms. deleting 500000 records took 10456 ms. Test-case-2 passed The output of make submit3: echo “Compiling test-case 3” Compiling test-case 3 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test3 test3.c -ldsa -lpa2 -lm ./test3 100000 Creating 100000 uids took 78 ms. adding 100000 records took 32 ms. making 599982 friends took 199 ms. search 100000 records took 23 ms. Test-case-3 passed ./test3 1000000 Creating 1000000 uids took 1600 ms. adding 1000000 records took 641 ms. making 5999982 friends took 4231 ms. search 1000000 records took 590 ms. Test-case-3 passed The output of make submit4: echo “Compiling test-case 4” Compiling test-case 4 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test4 test4.c -ldsa -lpa2 -lm ./test4 100000 Creating 100000 uids took 78 ms. adding 100000 records took 32 ms. making 599982 friends took 197 ms. deleting 50000 records took 455 ms. Test-case-4 passed ./test4 1000000 Creating 1000000 uids took 1549 ms. adding 1000000 records took 630 ms. making 5999982 friends took 4158 ms. deleting 500000 records took 10068 ms. Test-case-4 passed
1 Introduction In this assignment, you are to implement dynamic arrays to store a sequence of records. You are also required to sort the array using merge sort, quick sort, and selection sort and compare the time taken by these approaches. You also need to implement linear and binary search algorithms and compare the performance of these approaches. Since the binary search algorithm only works for the key used for sorting, you need to sort the array using different keys to facilitate fast searching for different kinds of queries. You need to implement the dynamic arrays with geometric expansion approach, as discussed in class. Initially, the array size is zero. During the first insertion, you need to create an array of size one. For subsequent insertions, if the array is full, you need to create a new array of double size, copy the contents of the old array to the new array, delete the old array, and insert the element in the new array. During the deletion, if you want to delete an element at a given position i, if i is the last element, decrease the array size by one; otherwise, copy the last element to position i before decreasing the array size by one. After the deletion, if only N/4 space is occupied the array, where N is the size of the array, create a new array of size N/2, copy the elements from the old array to the new array, and delete the old array. We call it a shrink operation. In this assignment, you are to store a sequence of struct record values in the dynamic array. A struct record definition is as follows. #define MAX_LEN 16 struct record { /* character string terminated with ’’ * maximum length is 16 */ char name[MAX_LEN]; /* a character array of 16 characters * not-necessarily terminated with ’’ * anywhere in the character array */ char uid[MAX_LEN]; int age; /* location */ struct location loc; /* list of posts */ struct list_tri *posts; /* list of friends */ struct list_rec *friends; /* needed for shortest Path */ int status; struct record *pred; /* needed for the tree data-structure */ int height; struct record *left; struct record *right; struct record *parent; }; For this assignment, only name, uid, and status fields are relevant. You can ignore the values of other fields. You are not allowed to make any changes in struct record. You need to store the starting address of the dynamic array in the variable record arr provided in the skeleton code. This variable is initialized to NULL. You can think of NULL as an invalid address. After every expansion or shrink operation, you need to store the starting address of the new array in the record arr variable. 3 Sorting and searching uids [1 mark] You need to implement merge sort, quick sort, and selection sort algorithms to sort the array using uid field in the struct record as a key. uid contains a unique 16-byte identifier corresponding to a record. This is not a string, i.e., ‘’ can also be part of the uid and appear multiple times in the array. You can directly use cmp uid routine from the skeleton code that compares two uids and return -1, 0, and 1 if the first uid is less than, equal, and greater than the second uid, respectively. You need to implement two search algorithms, linear search and binary search, to search a record corresponding to a particular uid and compare the performances of these algorithms. 4 Sorting and searching names [1 mark] In this part, you need to find the number of records corresponding to a given name. Notice that the name field in struct record is a ‘’ terminated character string. One way of implementing this is linear search, but it is inefficient. The other strategy would be to sort the array using name as a key and then use binary search to find a record with the given name and traverse the nearby elements to find the total number of records corresponding to a name. You need to implement both strategies and compare the performance of both algorithms. You need to use the quick sort algorithm for this part. 5 Library interface In this assignment, you need to implement a library that implements all the functionalities we discussed above. The user interface for your library is given in the “pa1.h” file. Below is the short description of these interfaces. search record linear: Use the linear search algorithm to find the record corresponding to the input uid. If there is no matching record, return a dummy record with −1 in the status field. search record binary: Use the binary search algorithm to find the record corresponding to the input uid. If there is no matching record, return a dummy record with −1 in the status field. sort records quick: Use the quick sort algorithm to sort the record arr using uid as the key. sort records merge: Use the merge sort algorithm to sort the record arr using uid as the key. sort records selection: Use the selection sort algorithm to sort the record arr using uid as the key. get num records with name linear: Find the number of records corresponding to the input name using the linear search algorithm. get num records with name binary: Find the number of records corresponding to the input name using the binary search algorithm. rearrange data: Use the quick sort algorithm to sort the record arr using name as the key. get num records: Return the total number of records present in the record arr. get record arr: Returns the starting address of the dynamic array. The implementation is already provided. Don’t change this implementation. 6 Compilation and running the test cases Clone the assignment repository using: git clone https://github.com/Systems-IIITD/DSALAB.git Implement everything in the “PA1/pa1.c” file. Don’t change any other files. Use printf to debug your code. Run “make” in the “PA1” folder to compile your library and test cases. There are three test cases. To run the first test cases: use “./test1 10”. It will test your program for ten records. Once your implementation works for small sizes, test and debug it for large sizes. To run the second test for size 10, use “./test2 10”. To run the third test case for size 10, use “./test3 10”. We will test your implementation for large input sizes. So make sure to test them for large inputs as well. You are not allowed to use malloc and free directly in your library. Use allocate memory and free memory routines provided to you instead of malloc and free. 6.1 How to submit Sample report file. The output of make submit1: echo “Compiling test-case 1” Compiling test-case 1 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test1 test1.c -ldsa -lpa1 -lm ./test1 10000 Running TEST1 for 10000 inputs Creating 10000 uids took 13 ms. adding 10000 records took 2 ms. deleting 10000 records took 20 ms. TEST-1 successful ./test1 100000 Running TEST1 for 100000 inputs Creating 100000 uids took 230 ms. adding 100000 records took 15 ms. deleting 100000 records took 4779 ms. TEST-1 successful The output of make submit2: echo “Compiling test-case 2” Compiling test-case 2 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test2 test2.c -ldsa -lpa1 -lm ./test2 100000 Running TEST2 for 100000 inputs Creating 100000 uids took 263 ms. adding 100000 records took 12 ms. linear search 20000 records took 2288 ms. quick sort 100000 records took 15 ms. binary search 100000 records took 28 ms. inserting 100000 records took 17 ms. merge sort 100000 records took 30 ms. binary search 100000 records took 35 ms. inserting 20000 records took 4 ms. selection sort 20000 records took 171 ms. binary search 20000 records took 3 ms. TEST-2 successful ./test2 1000000 Running TEST2 for 1000000 inputs Creating 1000000 uids took 4267 ms. adding 1000000 records took 131 ms. linear search 20000 records took 13138 ms. quick sort 1000000 records took 223 ms. binary search 1000000 records took 519 ms. inserting 1000000 records took 108 ms. merge sort 1000000 records took 398 ms. binary search 1000000 records took 506 ms. inserting 20000 records took 2 ms. selection sort 20000 records took 173 ms. binary search 20000 records took 3 ms. TEST-2 successful The output of make submit3: echo “Compiling test-case 3” Compiling test-case 3 gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test3 test3.c -ldsa -lpa1 -lm ./test3 100000 Running TEST3 for 100000 inputs Creating 100000 uids took 279 ms. adding 100000 records took 17 ms. linear search 20000 records took 8262 ms. quick sort 100000 records took 19 ms. binary search 100000 records took 365 ms. TEST-3 successful ./test3 1000000 Running TEST3 for 1000000 inputs Creating 1000000 uids took 3845 ms. adding 1000000 records took 116 ms. linear search 20000 records took 132444 ms. quick sort 1000000 records took 276 ms. binary search 1000000 records took 41411 ms. TEST-3 successful 7 Bonus part In this part, you need to implement a worst-case O(n) algorithm to find the median and use that as the pivot in your implementation of quick sort. You can find an O(n) algorithm in Chapter-9.3 of the CLRS book. If you do the bonus assignment, dump the implementation of your median finding algorithm after the outputs of make submit. Also, justify why your implementation is O(n). Referring to the book will not be considered a valid justification. Don’t submit any additional files apart from the “pa1.c” and your report.
Your friend, George P. Brudell, has to write a program to multiply very large square matrices for his special problems class. He also noticed that their matrices have many zeros in them, making them quite sparse. He decided to store his matrices as an array of (row, col, value) tuples instead of the standard 2D format. But now he’s stuck since he does not know how to perform efficient parallel sparse matrix multiplication using this representation of his. He asked you for help since he heard you are taking the HPC class this semester. Your job is to figure out an efficient parallel algorithm to perform sparse matrix multiplication where the matrices are stored as arrays of (row, col, value) tuples. Give the parallel runtime for your algorithm as a function of the total number of non-zero elements in the matrix. Then write a C/C++ parallel program to perform sparse matrix multiplication using George’s representation and show strong scaling of your implementation for different sized matrices and different sparsity parameters. Compare your experimental observation with the theoretical analysis of your algorithm and explain your findings. DO NOT PUBLISH PROJECT SOLUTIONS PUBLICLY. 2 Code framework 2.1 Input & Output format There is no input file in this project. You’ll have to provide an output file if ‘print results’ parameter is set to 1 in the command line. In that output file, you’ll have to print the two matrices you generate and their multiplication result in standard 2D format (not George’s sparse format). Sample output files are provided for reference in the Programming Assignments folder on Canvas. Sample command line argument: n: Dimension of the square matrices is n × n s: Sparsity parameter ∈ (0,1] pf: Print flag (results) ∈ {0,1} out: Output file name Sample command line input: $ mpirun -np 8 ./spmat 10000 0.001 0 spmat out 2.2 Implementation details Let’s assume you are supposed to perform the matrix multiplication of A×B = C in a p processor parallel computer. • Write a sparse matrix generator that generates (n/p) rows of matrix A and B using a random number of generator and that assigns 0 to the (i,j)-th element of the matrix with Probability (1 − s) [s is the sparsity parameter given in the command line]. • The runtime of the sparse matrix multiplication algorithm must depend upon the number of non-zero elements in the matrix and must be faster than the dense matrix multiplication algorithms presented in class. Please strictly adhere to George’s data structure and do not represent the matrix in any other form, except for the output matrix. • Each element of the matrix will be a 64 bit unsigned integer. To make things simple, you are allowed to store the output of the matrix multiplication in dense 2D format (using n × n entries), but both the inputs must be stored and processed in George’s sparse format. • Transpose the sparse B matrix such that each processor now stores n/p columns locally (in the same sparse format) using MPI Alltoallv collective operation. • Your program must embed a ring topology for all the p processors using the MPI’s embedding functions, and use the ring topology for the algorithm. • Rotate the B matrix using that ring topology such that all rows of A matrix can perform the dot products with all the columns of B matrix to compute the corresponding elements of the resulting C matrix. • For simplicity, we are storing the C matrix in dense 2D array format in 1D block distributed fashion. That means, the first processor stores first n/p rows (n2/p elements) of C, the second processor stores next n/p rows, ···. • (Bonus points) Come up with your own data structure and algorithm for sparse matrix multiplication. Explain your data structure, algorithm, and it’s performance in the report. You are free to implement your algorithm however way you find it useful, as long as it uses no extra library (other than standard C++ STL library) and written purely in MPI. • When the print flag 1 in command line, you are supposed to print matrix A, matrix B and then matrix C, (all in dense 2D array format) in the filename given in the command with an empty line after one another. 2.3 Deliverables The programming assignment is to be done in groups of three. It is important that you strictly adhere to the command line arguments and the output format described in the programming assignment. No matter how you decide to share the work amongst yourselves, each student is expected to have full knowledge of the submitted program. To submit the programming assignment, turn in the following: 1. Create a Makefile for your program, and make sure the name of your output executable isspmat. If you are not familiar with creating Makefiles, check the resources below. 2. Write a README.txt briefly describing how your program works and the machine you used for generating the results. 3. Experimentally evaluate and compare the performance of your program with varying inputmatrix sizes. For p = 16, plot the run-time of sparse matrix multiplication using three different n (> 1000) parameters by keeping e = 0.01 fixed. Next, plot the runtime of your program by fixing n ≥ 10000 and changing e = 0.1,0.01,0.001 using p = 2,4,8,16 processors. 4. Theoretically analyze the runtime of your parallel algorithm and discuss if the experimentalresults supports your analysis or not. Provide explanations if your experimental performance doesn’t match your theoretical analysis. 5. For bonus points, your own data structure and implementation must be ≥ 2× faster than George’s original algorithm. Any solution that deliberately writes a slow implementation of the original algorithm will be negatively penalized. Try to come up with some important observations on your program. We are not asking that specific questions be answered but you are expected to think on your own, experiment and show the conclusions along with the evidence that led you to reach the conclusions. Any irregular or unexpected results should also be noted and explained why it is unavoidable. Include your plots and observations in a PDF file with name report.pdf. Make sure to list names of all your teammates at the very beginning of your report. Provide a brief description of your implementation along with space and run-time analysis, and include a table at the end containing the contributions of each team member. 6. Submit the following: (a) All the source files and the Makefile in “Programming Assignment 3 Code” on Gradescope. Do not upload the executable file in your submission. (b) The report in “Programming Assignment 3 Report” on Gradescope. Only one student needs to make the submission for the whole group. If students of the same group makes two different submissions, there would be a minor penalty applied. 3 Grading (100 pts + 30 bonus pts) The program will be graded on correctness and usage of the required parallel programming features. You should also use good programming style and comment your program so that it is understandable. Grading consists of the following components: 1. Correctness (40 pts) • Automated tests on Gradescope that will test your program functionality for various inputs including all corner cases. 2. Code and Performance (40 pts) • We will go through your code to make sure appropriate parallel programming practices discussed in the class are being followed along with the right MPI functions being called. • Specifically, we will make sure that (a) you are generating the matrices properly in George’s sparse format based on the command line arguments, (b) your implementations follows the structure of the algorithm mentioned and format mentioned previously. • We will also check the implementations for: – No serialization in your implementation – Efficient data transfer among processes – Appropriate use of MPI collectives and/or point-to-point operations – Proper use of ring topology Note: Points will be deducted for ignoring performance protocols; Serialization in the program will lead to a zero on the whole assignment. This includes unnescessary serialization of point-to-point communications. 3. Report (20 pts) • Explain the time and space complexities of your implementation (4 pts) • The mentioned plots (8 pts) • Empirical analysis, observations, and conclusion (8 pts) 4. Bonus (30 pts) • Perform the same experiments of your own algorithm and data structure for sparse matrix multiplication and describe it in the report. Explain why your new algorithm is faster than George’s original plan. 4 Resources 1. What is a Makefile and how does it work?: https://opensource.com/article/18/8/what-howmakefile 2. PACE ICE cluster guide: Link here.
Write a C/C++ parallel program to transpose a square matrix using your own implementations of the all-to-all communication primitive. You will implement the two algorithms for the all-to-all primitive discussed in class, i.e., one using hypercubic permutations, and the other using arbitrary permutations. You will then compare the runtime of transposing matrix using your all-to-all implementations and MPI Alltoall. Fixing the number of processors to 8 and 16, plot the runtimes of the three approaches over different matrix sizes and describe your observations of the results. Provide a brief introduction of your code or details specific to your implementations. Contrast the performance of your implementations with the MPI provided implementation. DO NOT PUBLISH PROJECT SOLUTIONS PUBLICLY. 2 Code framework 2.1 Input & Output format The program should take 4 command line arguments – input file, output file, all-to-all algorithm choice and matrix size n. You have to structure the program such that one processor (with rank 0) reads the input file and block distribute the rows among all the processors using MPI Scatter. We are doing this for convenience sake, and because we do not have a machine that supports truly parallel I/O. Note that when you time your algorithm, you should start the timer after the data has been block distributed and end it before you gather the transposed matrix to write to the output file. Sample input and output files are provided for reference in the Programming Assignments folder on Canvas. All-to-all algorithm command line arguement: a: Arbritary all-to-all (Implemented by you) h: Hypercubic all-to-all (Implemented by you) m: MPI Alltoall Sample command line input: $ mpirun -np 8 ./transpose matrix.txt transpose.txt a 24 2.2 All-to-all implementation details 2.3 Deliverables The programming assignment is to be done in groups of three. It is important that you strictly adhere to the input format described in the programming assignment. No matter how you decide to share the work amongst yourselves, each student is expected to have full knowledge of the submitted program. To submit the programming assignment, turn in the following: 1. Create a Makefile for your program, and make sure the name of your output executable istranspose. If you are not familiar with creating Makefiles, check the resources below. 2. Write a README.txt briefly describing how your program works and the machine you used for generating the results. 3. Experimentally evaluate and compare the performance of your program with varying inputmatrix sizes. For p = 8 and p = 16, plot the run-time of matrix transpose using both of your all-to-all implementations and MPI Alltoall as a function of the problem size. Try to come up with some important observations on your program. We are not asking that specific questions be answered but you are expected to think on your own, experiment and show the conclusions along with the evidence that led you to reach the conclusions. Any irregular or unexpected results should also be noted and explained why it is unavoidable. Include your plots and observations in a PDF file with name report.pdf. Make sure to list names of all your teammates at the very beginning of your report. Provide a brief description of your implementation along with space and run-time analysis, and include a table at the end containing the contributions of each team member. 4. Submit the following: (a) All the source files and the Makefile in “Programming Assignment 2 Code” on Gradescope. Do not upload the executable file in your submission. (b) The report in “Programming Assignment 2 Report” on Gradescope. Only one student needs to make the submission for the whole group. If students of the same group makes two different submissions, there would be a minor penalty applied. 3 Grading (100 pts total) The program will be graded on correctness and usage of the required parallel programming features. You should also use good programming style and comment your program so that it is understandable. Grading consists of the following components: 1. Correctness (50 pts) • Automated tests on Gradescope that will test your program functionality for various inputs including all corner cases. 2. Code and Performance (30 pts) • We will go through your code to make sure appropriate parallel programming practices discussed in the class are being followed along with the right MPI functions being called. • Specifically, we will make sure that (a) all-to-all functions are utilized efficiently to transpose the input matrix and (b) both all-to-all implementations follows the structure of the algorithms for the hypercubic and arbitary permutations in the slides. • We will also check the implementations for: – Proper load distribution – Efficient data transfer among processes – Appropriate uses of only point-to-point communications for the all-to-all implementations Note: Points will be deducted for ignoring performance protocols; Serialization in the program will lead to a zero on the whole assignment. This includes unnescessary serialization of point-to-point communications. 3. Report (20 pts) • The two plots (8 pts) • Theoretical analysis for space and time complexities for both all-to-all implementation and the matrix transpose (4 pts) • Empirical analysis, observations, and conclusion (8 pts). 4 Resources 1. What is a Makefile and how does it work?: https://opensource.com/article/18/8/what-howmakefile 2. PACE ICE cluster guide: Link here.
1 Problem Statement Write a parallel program in C/C++ to estimate the value of π using the Monte Carlo method specified below. The program should take n as input, which is the number of points to be used for the estimation. The program should then generate n random points in the unit square [0,1] × [0,1] and count the number of points that lie inside the unit circle. Let n be a large integer, then estimated value of π is 4 · number of points in the circleFigure 1: Estimating π using Monte Carlo method 2 Parallel Algorithm The estimation can be easily parallelized by assigning each processor the responsibility for distinct points. You should use the following MPI functions: • Have processor with rank 0 read n, and use MPI Bcast to broadcast it to all processors. • Use MPI Reduce function to sum the number of points in the circle across all processors. • Use MPI Wtime to time the run-time of the program (measure on processor 0). For the random number generator, you can use the rand() function in C/C++. However, you should make sure that the random number generator is seeded differently for each processor. You can use the processor rank for this purpose. For example, if the rank of the processor is i, then you can use srand(time(NULL) + i) to seed the random number generator on that processor. 3 Code framework 3.1 Input & Output Format Your program should take n as the input using command line arguments and output the estimated value of π and the time taken to compute this value (comma-separated). For example, if the estimated value is s and the time taken is t, your output should be “s, t”. (Note: s should be printed up to 12 decimal points). All output is done through processor with rank 0. 3.2 Deliverables 1. Create a Makefile for your program, and make sure the name of your output executable is“pi calc”. If you are not familiar with creating Makefiles, check resources below for help. 2. Write a “README.txt” briefly describing how your program works and the machine you used for generating the results. 3. For n = 106, plot a graph of run-time of the program vs. the number of processors for a few chosen values of p. This run-time should include all computations that contribute to the estimation, including any local computations and global reductions. Include your graph and observation regarding the speedup in a PDF file with name “report.pdf”. Make sure to list names of all your teammates at the very beginning of your report. 4. Submit your a) “code.zip” in “Programming Assignment 1 – Code” on Gradescope. Your zip file should include all the .cpp files, Makefile and README.txt file; b) your report in “Programming Assignment 1 – Report” on Gradescope. 4 Resources 1. What is a Makefile and how does it work?: https://opensource.com/article/18/8/what-howmakefile 2. PACE ICE cluster guide: https://docs.pace.gatech.edu/ice cluster/ice-guide/. Documentation for writing a PBS script: https://docs.pace.gatech.edu/software/PBS script guide/
1 Overview In this assignment, you will be building a neural conditional random field (CRF) for the task of constituency parsing. You only need to implement the inside algorithm for the CRF as part of your model’s forward pass. The rest of the system is provided in the starter code. After introducing the task and modeling approach in Sections 2–3, we provide implementation instructions in Section 4. Finally, we describe deliverables in Section 5 and optional extensions to the project in Section 7. 2 Constituency Parsing Constituency Parsing [1, 2] is a type of syntactic parsing, which is the task of assigning a syntactic structure to a sentence. For example: I shot an elephant in my pajamas. can be parsed in two ways as Figure 1 shown.Figure 1: Two parse trees for an ambiguous sentence. The parse on the left corresponds to the humorous reading in which the elephant is in the pajamas, the parse on the right corresponds to the reading in which Captain Spaulding did the shooting in his pajamas. For this assignment, you will be using data from the English WSJ Penn TreeBank (PTB) to learn a constituency parser. In the dataset itself, trees are represented as flattened strings with brackets and labels. For example, (TOP (S (NP (NNP Ms.) (NNP Haag)) (VP (VBZ plays) (NP (NNP Elianti))) (. .))) In the codebase, we provide a Dataloader() module to load the string trees and a draw_tree() method to visualize the trees (rendered as below).Figure 2: Constituency tree example. 3 LSTM-CRFs for Constituency ParsingWe use Bi-LSTMs, MLPs (multilayer perceptrons), and Biaffine functions to obtain a scoring function φ for the task. Then, similar to the previous project on Name Entity Recognition (NER), we use a Conditional Random Field (CRF) layer to incorporate constituency structure among words. We will describe each component and the decoding and learning algorithm in details in the following parts. Bi-LSTM features. As we’ve learned from lectures and the previous two assignments, recurrent neural networks (RNNs) are a natural choice for computing learned feature representations of sequences. Given a sentence with POS tags, X = {W,G}, we encode it as sequence of word embedding vectors w1 …wT and tag embedding vectors g1 …gT before passing it to the model. The word embedding and tag embedding and the same position are simply concatenated. xt = CONCAT(wt,gt), We then apply a Bi-LSTM to this embedding sequence. −→ (1) h t = tanh(Wihxt + bih + Whhh(t−1) + bhh). (2) For bidirectional RNNs, hidden states −→h t,←−h t are computed in forward and backward directions, respectively, and concatenated to obtain ht = h−→h t;←−h ti. Boundary representation. We apply two separate MLPs, MLPleft and MLPright, to ht, to create feature representations of both left and right span endpoints. rlefti = MLPleft(ht) (3) rrighti = MLPright(ht) (4) Biaffine scoring function. The biaffine scoring layer was first introduce in [3]. Given the left and right span representations, rlefti , rrighti , for each position i, we score each candidate span (i,j) using a biaffine operation over the left boundary representation ri and the right boundary representation rj, using an intermediate parameter matrix, wlabell , that depends on the label l. Thus, the score a span (i,j) with label l is given by: Biaffine (5) (6) where w is a weight matrix for label l. And, accordingly, the vectorized version will be: (7) Note that, Wlabel is a tensor defined as . Factorizing the production rules. In the neural CRF we present here in this project, all labels are independent of one-another given X. This is not true in PCFGs. In this project, the CRF structure is just for enforcing tree-shape, while the BiLSTM will predict labels for spans independently. This means our factorization assumptions are simpler. For a full sentence X, its score is the product of all constituent spans’ scores: Φ(X,Y ) = Y φ(i,j,l) (8) (i,j,l)∈Y And the conditional log likelihood under the model is: Φ(X,Y ) logP(Y |X) = log P Y 0∈O(X) Φ(X,Y 0) (9) Here, O(X) denotes the set of valid binary trees over sentence X. CYKDecoding. Given the log values of the local scoring potentials we computed earlier, logφ(i,j,l), we can use the Cocke–Younger–Kasami (CYK) algorithm to obtain the best scoring constituency tree Yˆ (i.e. whose score is maximum among all the possible parse trees): Yˆ = argmaxY ∈O(X)P(Y |X) (10) = argmaxY ∈O(X)Φ(X,Y ) (11) The original CYK is a dynamic programming algorithm with O(n3 · |R|) complexity, where R is the set of all possible production rules in the underlying PCFG. However, in a neural CRF parser, we actually make the parent label and child label independent in our parametrization (see Eq. 8). Therefore, the CYK decoding algorithm in this assignment is just O(n3) time complexity (if the maxes in the pseudo-code below are pre-computed and cached). We provide an implementation of the algorithm in the CSE291 repository, and the pseudo-code (non-batched version) is as below. Input: Score: a scoring matrix of shape [T, T, L] # stores the logs of the phi scores computed earlier T: length of sentence L: the number of labels Output: Result: a result matrix of shape [T, T] # stores the scores of best sub-trees for each span Algorithm: # all the data are zero-indexed Initialize matrix Result with -inf For i = 0 to T – 1: Result[i, i] = 0 For d = 2 to T: # for each span length For i = 0 to T – d: # for each start j := i + d – 1 # end of span For k = i to j – 1: # for each split point of span Result[i, j] := max(Result[i, j], max(Score[i, j, *]) + Result[i, k] + Result[k+1, j]) Return Result Learning. In order to estimate model parameters θ, we minimize the negative log likelihood over entire sequences in the dataset {X,Y∗}: X,Y∗ X,Y∗ NLL = X −logp(Y ∗ | X;θ) = X −hlogΦ(X,Y ∗) − log X Φ(X,Y 0)i (12) Y 0∈O(X) To compute the partition function, logPY ∈O(X) Φ(X,Y ), we can use an algorithm similar to the CKY algorithm we defined above for decoding from the model. Given all the log scores scores of labeled spans with from the biaffine function (technically, this will be a 3 dimensions matrix of shape [seq_length, seq_length, n_labels]), we can define pseudo-code for computing the partition function: Input: Score: a scoring matrix of shape [T, T, L] # stores the logs of the phi scores computed earlier T: length of sentence L: the number of labels Output: S:aresultmatrixofshape[T,T],whereS[0,T-1]isthelogpartitionfunction Algorithm: # all the data are zero-indexed Initialize matrix S with -inf for i = 0 to T – 1: S[i, i] = 0 For d = 2 to T: # for each span length For i = 0 to T – d: # for each start j := i + d – 1 # end of the span For k = i to j – 1: # for each split point of span S[i, j] := logSumExp(S[i, j], logSumExp(Score[i, j, *]) + S[i, k] + S[k+1, j]) Return S In the starter code, we also provide some comments to help you understand how to implement the algorithm. All you need is to fill in the missing part of function inside(). You are allowed to implement it in your own way. However, we would suggest that you implement the vectorized version of it. Otherwise, your training process would significantly slow down on colab. To implement the vectorized version, you will need first understand how the CYK decoding is implemented. You will find the helper function stripe() and the PyTorch’s Tensor operator diag() helpful in implementing the vectorized version. Evaluation. The constituency trees in PTB data are n-array trees. However, our model actually reasons about Chomsky Normal Form (CNF) trees. In the provided evaluation script, we first convert the prediction back to an n-array tree and then compute the recall, precision, and F1 score. 4 Implementation Instructions Implement the inside algorithm of the CRF layer defined above and use it for the task of Constituency Parsings. You are encouraged to clone and use the starter code from the CSE291 repository , which includes portions of the PTB data train/dev splits, data loading functionality, and evaluation using (labeled/unlabeled) span-based precision, recall, and F1 score. The only part you need to implement is to add the required Inside algorithm for CRF negative log likelihood learning. Here’s the best scoring evaluation result on ./data/PTB_first_2000 (A full training log is also attached in the appendix for reference): dev: loss: 0.6538 – UCM: 18.76% LCM: 17.35% UP: 84.74% UR: 86.06% UF: 85.40% LP: 82.59% LR: 83.87% LF: 83.23% where UCM/LCM stands for Unlabeled Complete Match, UP/LP stands for Unlabeled/Labeled Precision, UR/LR stands for Unlabeled/Labeled Recall, UF/LF stands for Unlabeled/Labeled F1. As a reminder, we will not be grading based on the absolute performance of your method as long as it performs reasonably well, indicating it is implemented correctly. If you approximately match the F1 numbers we provide above, you should expect you’ve implemented the algorithm correctly. 5 Deliverables Please submit a 1–2 page report along with the source code on Gradescope. We suggest using the ACL style files, which are also available as an Overleaf template. The core of this project is about implementing the inside algorithm for a neural CRF parser. Thus, we don’t require as much analysis as in past projects. We ask you to briefly describe the overall approach, e.g. paraphrase the model description and math in your own words. Then we ask you briefly describe any specific design choices you made (e.g. how you vectorized your inside algorithm if you choose to do so). Then we ask you to present your evaluation results and runtime. Finally, we ask you to present two example predicted test trees and comment on errors you see vs. the ground-truth trees for the same examples. Shorter reports are fine for this project, e.g. 1-2 pages, though feel free to write more if you want to do additional analysis, try additional features (not required for full credit). 6 Useful References While you can use the Parser package as a reference, the code in your implementation must be your own. Note that the model of constituency parsing in the package is different from that of our assignment. 7 Optional Extensions • Simplify the neural architecture and compare it with our default model. For example, you can remove the tagging embedding layer, or use the same MLP layer (instead of two different MLP layers) to model the boundary representation r. • Choose a pre-trained language model (like BERT or GloVe) and use its embeddings as input to the CRF model. Or use a char-level LSTM layer to encode words instead of directly using an embedding layer. • Add a discrete grammar (e.g. X-bar or one read directly off the treebank) to constrain your neural CRF parser – e.g. not all triples of parent label, left child label, and right child label are permitted under real discrete grammars. • Change the biaffine scoring function to capture interactions between parent and child labels – i.e. learn a full neural grammar! • Choose your own adventure! Propose and implement your own analysis or extension. You are allowed to discuss the assignment with other students and collaborate on developing algorithms – you’re even allowed to help debug each other’s code! However, every line of your write-up and the new code you develop must be written by your own hand. References Appendix The full training log is as below. !cse291ass3 python main.py –batch-size 128 Building the fields Namespace(batch_size=128, bos_index=2, buckets=32, clip=5.0, delete={’’, ’.’, ’,’, “’’”, ’?’, ’!’, ’S1’, ’:’, ’-NONE-’, ’‘‘’, ’TOP’}, dev=’data/ptb/dev.pid’, device=’cuda’, embed=None, encoder=’lstm’, eos_index=3, epochs=10, eps=1e-12, equal={’ADVP’: ’PRT’}, feat=None, lr=0.002, max_len=None, mu=0.9, n_embed=100, n_labels=71, n_tags=45, n_words=3511, nu=0.9, pad_index=0, test=’data/ptb/test.pid’, train=’data/ptb/train.pid’, unk=’unk’, unk_index=1, weight_decay=1e-05) Building the model Model( (word_embed): Embedding(3511, 100) (tag_embed): Embedding(45, 100) (embed_dropout): Dropout(p=0.33, inplace=False) (encoder): LSTM(200, 400, num_layers=3, dropout=0.33, bidirectional=True) (encoder_dropout): Dropout(p=0.33, inplace=False) (mlp_l): MLP(n_in=800, n_out=100, dropout=0.33) (mlp_r): MLP(n_in=800, n_out=100, dropout=0.33) (feat_biaffine): Biaffine(n_in=100, n_out=71, bias_x=True, bias_y=True) (crf): CRFConstituency() (criterion): CrossEntropyLoss() ) train: Dataset(n_sentences=2000, n_batches=409, n_buckets=32) dev: Dataset(n_sentences=1700, n_batches=342, n_buckets=32) test: Dataset(n_sentences=2416, n_batches=484, n_buckets=32) Epoch 1 / 10: 0 iter of epoch 1, loss: 4.9900 50 iter of epoch 1, loss: 1.7499 100 iter of epoch 1, loss: 1.0927 150 iter of epoch 1, loss: 1.3784 200 iter of epoch 1, loss: 0.6478 250 iter of epoch 1, loss: 0.8427 300 iter of epoch 1, loss: 1.0710 350 iter of epoch 1, loss: 0.6919 400 iter of epoch 1, loss: 0.9706 dev: loss: 0.8141 – UCM: 8.71% LCM: 7.41% UP: 77.13% UR: 80.77% UF: 78.91% LP: 74.12% LR: 77.63% LF: 75.84% Epoch 2 / 10: 0 iter of epoch 2, loss: 0.9249 50 iter of epoch 2, loss: 0.5275 100 iter of epoch 2, loss: 0.8728 150 iter of epoch 2, loss: 0.7860 200 iter of epoch 2, loss: 0.8848 250 iter of epoch 2, loss: 1.0504 300 iter of epoch 2, loss: 0.5526 350 iter of epoch 2, loss: 1.1311 400 iter of epoch 2, loss: 0.8681 dev: loss: 0.6986 – UCM: 12.47% LCM: 10.76% UP: 81.49% UR: 83.45% UF: 82.46% LP: 78.86% LR: 80.76% LF: 79.79% Epoch 3 / 10: 0 iter of epoch 3, loss: 0.7196 50 iter of epoch 3, loss: 0.3954 100 iter of epoch 3, loss: 1.0758 150 iter of epoch 3, loss: 0.3884 200 iter of epoch 3, loss: 0.7023 250 iter of epoch 3, loss: 0.6243 300 iter of epoch 3, loss: 0.5182 350 iter of epoch 3, loss: 0.5139 400 iter of epoch 3, loss: 0.5725 dev: loss: 0.6529 – UCM: 14.88% LCM: 13.59% UP: 83.02% UR: 84.66% UF: 83.83% LP: 80.62% LR: 82.20% LF: 81.40% Epoch 4 / 10: 0 iter of epoch 4, loss: 0.6344 50 iter of epoch 4, loss: 0.4191 100 iter of epoch 4, loss: 0.6893 150 iter of epoch 4, loss: 0.5572 200 iter of epoch 4, loss: 0.9136 250 iter of epoch 4, loss: 1.1216 300 iter of epoch 4, loss: 0.6391 350 iter of epoch 4, loss: 0.5298 400 iter of epoch 4, loss: 0.8414 dev: loss: 0.6712 – UCM: 15.41% LCM: 14.18% UP: 81.03% UR: 84.04% UF: 82.51% LP: 78.68% LR: 81.60% LF: 80.11% Epoch 5 / 10: 0 iter of epoch 5, loss: 0.4830 50 iter of epoch 5, loss: 0.5475 100 iter of epoch 5, loss: 0.7482 150 iter of epoch 5, loss: 0.9239 200 iter of epoch 5, loss: 0.3832 250 iter of epoch 5, loss: 0.6287 300 iter of epoch 5, loss: 0.4790 350 iter of epoch 5, loss: 0.4887 400 iter of epoch 5, loss: 0.5246 dev: loss: 0.6426 – UCM: 17.24% LCM: 16.00% UP: 84.04% UR: 85.02% UF: 84.53% LP: 81.96% LR: 82.92% LF: 82.44% Epoch 6 / 10: 0 iter of epoch 6, loss: 0.6358 50 iter of epoch 6, loss: 0.3243 100 iter of epoch 6, loss: 0.4326 150 iter of epoch 6, loss: 0.2156 200 iter of epoch 6, loss: 0.2075 250 iter of epoch 6, loss: 0.3221 300 iter of epoch 6, loss: 0.6566 350 iter of epoch 6, loss: 0.3273 400 iter of epoch 6, loss: 0.4782 dev: loss: 0.6857 – UCM: 17.71% LCM: 16.24% UP: 85.12% UR: 84.78% UF: 84.95% LP: 83.04% LR: 82.71% LF: 82.88% Epoch 7 / 10: 0 iter of epoch 7, loss: 0.6639 50 iter of epoch 7, loss: 0.2892 100 iter of epoch 7, loss: 0.4901 150 iter of epoch 7, loss: 0.4327 200 iter of epoch 7, loss: 0.3621 250 iter of epoch 7, loss: 0.4680 300 iter of epoch 7, loss: 0.3519 350 iter of epoch 7, loss: 0.3976 400 iter of epoch 7, loss: 0.2718 dev: loss: 0.6737 – UCM: 18.00% LCM: 16.65% UP: 84.99% UR: 84.80% UF: 84.89% LP: 83.04% LR: 82.86% LF: 82.95% Epoch 8 / 10: 0 iter of epoch 8, loss: 0.2797 50 iter of epoch 8, loss: 0.4043 100 iter of epoch 8, loss: 0.4003 150 iter of epoch 8, loss: 0.3425 200 iter of epoch 8, loss: 0.5250 250 iter of epoch 8, loss: 0.6620 300 iter of epoch 8, loss: 0.2005 350 iter of epoch 8, loss: 0.7108 400 iter of epoch 8, loss: 0.5317 dev: loss: 0.6942 – UCM: 18.65% LCM: 17.41% UP: 84.95% UR: 85.95% UF: 85.45% LP: 82.77% LR: 83.75% LF: 83.26% Epoch 9 / 10: 0 iter of epoch 9, loss: 0.5051 50 iter of epoch 9, loss: 0.7551 100 iter of epoch 9, loss: 0.5349 150 iter of epoch 9, loss: 0.3717 200 iter of epoch 9, loss: 0.3090 250 iter of epoch 9, loss: 0.5121 300 iter of epoch 9, loss: 0.8158 350 iter of epoch 9, loss: 0.4875 400 iter of epoch 9, loss: 0.5440 dev: loss: 0.6900 – UCM: 20.24% LCM: 19.00% UP: 84.65% UR: 86.30% UF: 85.47% LP: 82.43% LR: 84.04% LF: 83.23% Epoch 10 / 10: 0 iter of epoch 10, loss: 0.3559 50 iter of epoch 10, loss: 0.2764 100 iter of epoch 10, loss: 0.2985 150 iter of epoch 10, loss: 0.3805 200 iter of epoch 10, loss: 0.4140 250 iter of epoch 10, loss: 0.4455 300 iter of epoch 10, loss: 0.8627 350 iter of epoch 10, loss: 0.4133 400 iter of epoch 10, loss: 0.6942 dev: loss: 0.6538 – UCM: 18.76% LCM: 17.35% UP: 84.74% UR: 86.06% UF: 85.40% LP: 82.59% LR: 83.87% LF: 83.23%
1 Overview In this assignment, you will be building a neural conditional random field (CRF) for the task of named entity recognition (NER). After introducing the task and modeling approach in Sections 2–4, we provide implementation instructions in Section 5. Finally, we describe deliverables in Section 6 and optional extensions to the project in Section 8. 2 Named Entity Recognition Named Entity Recognition (NER) is a type of information extraction task with the goal of identifying and classifying word spans (sequences of consecutive words in a sentence) into categories such as person, organization, location, time, and quantity. NER is an important processing step used to extract keywords for applications such as structured knowledge base creation, dictionary building, search, and voice command understanding. The task is best illustrated with an example: Andrew Viterbi co-founded Qualcomm, a company headquartered in San Diego. After labeling each named entity span with its category: [Andrew Viterbi]person co-founded [Qualcomm]organization, a company headquartered in [San Diego]location. Even though, NER is a span/chunk identification and classification task, it is typically set up as a word tagging problem by annotating tokenized named entities with class-labeled Beginning-InsideOutside (BIO) tags. In this format, words outside named entity chunks are labeled with an ‘O’ tag and words inside named entity chunks are labeled with their class label prefixed with ‘I’. For entities that are immediately next to each other, the first word of the second entity gets labeled as ‘B’. For example, the above, tokenized sentence under this labeling scheme looks like this: Andrewi-per Viterbii-per co-foundedo Qualcommi-org ,o ao companyo headquarteredo ino Sani-loc Diegoi-loc .o For this assignment, you will be using data from the CoNLL-2003 Shared Task , which only considers 4 classes of named entities: persons, locations, organizations and names of miscellaneous entities that do not belong to the previous three groups.Figure 1: Neural network-based tagging models. On the left, a bidirectional RNN makes independent tag classifications per time step. On the right, a bidirectional RNN-CRF learns local sequential dependencies between neighboring output tags to predict the structured output tag sequence. Diagram based on [4]. 3 Baseline: RNN for NER As we’ve learned from lectures and the previous language modeling assignments, recurrent neural networks (RNNs) are a natural choice for computing learned feature representations of sequences. Given a labeled sentence {X,Y } composed of a sequence of word embedding vectors x1 …xT and tag embedding vectors y1 …yT, RNNs apply a learned recurrent function using input weights/bias Wih,bih and recurrent weights/bias Whh,bhh −→ h t = tanh(Wihxt + bih + Whhh(t−1) + bhh). (1) For bidirectional RNNs, hidden states −→h t,←−h t are computed in forward and backward directions, respectively, and concatenated to obtain ht = h−→h t;←−h ti. In order to predict the associated tag for time step t, we apply a logistic regression classifier on input features ht using learned weights/bias Wout,bout and the softmax function to obtain a probability distribution over the tag set vocabulary. ft = Woutht + bout (2) softmax(ft) (3) We show a diagram of a bidirectional RNN for NER on the left of Figure 1. (NB: We defined the model with a vanilla RNN for illustration, but you can (and probably should) use an LSTM here instead of an RNN.) Learning: Similar to the previous assignments, parameters can be learned by minimizing the sum of the negative log likelihood under the model parameters θ for each prediction at each time step over training set X,Y∗ using the ground truth tags at each time step denoted by y∗t: X,Y∗ T NLL (4) In practice, we compute the loss stochastically over batches instead. Decoding: We simply apply an argmax at each time step independently since each classification is performed independently. 4 Advanced: RNN-CRF for NER Although the RNN tagger (Sec. 3) produces rich, context-sensitive feature representations of the input sentence, the independent tag classification decisions on top of these features are suboptimal for sequence labeling. Without any dependency between tags, the model is unable to learn the constraints that are common to sequence labeling tasks. For instance, in NER i-per does not directly follow i-org, and in English part-of-speech tagging, adjectives only precede nouns. To remedy this, we can use a Conditional Random Field (CRF) layer to incorporate dependency structure between neighboring labels. The CRF, introduced in [3], is a class of globally normalized, discriminative model that estimates the probability of an entire sequence p(Y | X) in a log-linear fashion on feature potentials (i.e., nonnegative functions) Φ: Φ(X,Y ) p(Y | X;θ) = P Y 0∈O Φ(X,Y 0), (5) The denominator is also referred to as the “partition function’. The O in the denominator represents the set of all possible sequences of output tags over the input sentence. (NB: Strictly speaking, O should depend on the input sentence, X, since the length of the input determines the length of the tag sequence. We omit this dependence for notational brevity.) This can present a major computational burden unless we assume that Φ is composed of a bunch of local potential functions that only operate on the preceding local neighbor yt−1: . (6) Under this linear chain assumption, we can achieve tractable learning/decoding with dynamic programming algorithms. Instead of manually defining our feature potentials, which takes considerable human effort, we can automatically learn nonlinear features in a deep neural network. To do this, we can use our transformed RNN input feature potentials (or “emissions”), ft, from Sec. 3 as our log emission potentials. Our log transition potentials can simply be a square weight matrix U over the tag set representing the weight of the transition from one tag to the next. T Φ(X,Y ) = Yφemission(X,yt) · φtransition(yt−1,yt) (7) . (8) We show a diagram of a CRF layer on top of bidirectional RNN emissions on the right of Figure 1. Learning: In order to estimate model parameters θ, we minimize the negative log likelihood over entire sequences in the dataset {X,Y∗}: X,Y∗ X,Y∗ NLL = X −logp(Y ∗ | X;θ) = X −hlogΦ(X,Y ∗) − log X Φ(X,Y )i (9) Y ∈O Decoding: During decoding we aim to find the most likely tag sequence under the model parameters θ arg maxY ∈Op(Y | X;θ), (10) which can be computed exactly using the Viterbi algorithm (see pseudocode at Wikipedia ), which has a recurrence very similar to the Forward algorithm dynamic program. 5 Implementation Instructions Implement a linear chain CRF using the bidirectional recurrent parameterization defined above and use it for the task of NER. You are encouraged to clone and use the starter code from the CSE291 repository , which includes portions of the CoNLL-2003 Shared Task NER data train/dev splits, data loading functionality, and evaluation using span-based precision, recall, and F1 score. Additionally, we provide a bidirectional LSTM tagger baseline BiLSTMTagger based on Section 3 that performs independent classifications over the tag set at each time step. We suggest that you add the required Forward algorithm for CRF negative log likelihood learning and the Viterbi algorithm for exact CRF decoding on top of the existing BiLSTMTagger class. Using the provided evaluation procedure, we can visualize the chunk-level precision, recall, and F1 for each class of named entity. Here’s the best scoring evaluation result (72.42 avg Fβ=1) on the dev.data.quad for BiLSTMTagger after 30 epochs of training on train.data.quad (6 mins training time on Colab GPU, not vectorized or batched): processed 11170 tokens with 1231 phrases; found: 1180 phrases; correct: 873. accuracy: 75.00%; (non-O) accuracy: 94.42%; precision: 73.98%; recall: 70.92%; FB1: 72.42 LOC: precision: 83.85%; recall: 81.54%; FB1: 82.68 353 MISC: precision: 80.14%; recall: 58.85%; FB1: 67.87 141 ORG: precision: 62.25%; recall: 61.24%; FB1: 61.74 302 PER: precision: 71.88%; recall: 74.80%; FB1: 73.31 384 Andhere’sthebestscoringevaluationresult(74.03avgFβ=1)onthedev.data.quadforourBiLSTMCRFTagger (20 mins training time on Colab GPU, vectorized but not batched): processed 11170 tokens with 1231 phrases; found: 1141 phrases; correct: 878. accuracy: 75.72%; (non-O) accuracy: 94.56%; precision: 76.95%; recall: 71.32%; FB1: 74.03 LOC: precision: 87.65%; recall: 78.24%; FB1: 82.68 324 MISC: precision: 81.43%; recall: 59.38%; FB1: 68.67 140 ORG: precision: 68.86%; recall: 61.24%; FB1: 64.83 273 PER: precision: 72.28%; recall: 79.13%; FB1: 75.55 404 As a reminder, we will not be grading based on the performance of your method, but the quality of the presentation and analysis in your report write-up. 6 Deliverables Please submit a 2–3 page report along with the source code on Gradescope. We suggest using the ACL style files, which are also available as an Overleaf template. In your submission, you should describe your implementation choices and report performance using the evaluation code in the appropriate graphs and tables. In addition, we expect you to include some of your own investigation or error analysis. We are more interested in knowing what observations you made about the models or data than having a reiteration of the formal definitions of the various models. If you choose to complete an optional task, please present an analysis of your findings, along with the particular implementation decisions you made. 7 Useful References While you can use the following PyTorch tutorial as a reference, the code in your implementation mustbeyourown. http://pytorch.org/tutorials/beginner/nlp/advanced_tutorial.html 8 Optional Extensions • Choose a pre-trained language model (like BERT) and use its embeddings as input to the CRF model. • Add local, hand-designed features to your neural CRF by creating feature functions aimed to encode important information for the task of NER, such as capitalization, word form, or the presence of a word in a gazetteer. Do these features help performance in low-resource training scenarios? • Choose another sequence labeling task to apply your Neural CRF to. In your write-up, describe the task, the dataset, and the evaluation setup. Here are some suggested tasks: – Part of speech tagging in a language of your choice. How does the performance of your method scale with tag set size? – Co-reference resolution – NP Chunking (i.e., shallow parsing) – Word sense disambiguation • Extend your linear chain CRF into a semi-Markov CRF for NER that jointly segments the text into the appropriate named entity phrase class (PER, LOC, etc.) and tags them with the appropriate I/O label. • Choose your own adventure! Propose and implement your own analysis or extension. You are allowed to discuss the assignment with other students and collaborate on developing algorithms – you’re even allowed to help debug each other’s code! However, every line of your write-up and the new code you develop must be written by your own hand. References [1] Michael Collins. Log-Linear Models, MEMMs, and CRFs. [2] Zhiheng Huang, Wei Xu, and Kai Yu. Bidirectional lstm-crf models for sequence tagging. arXiv preprint arXiv:1508.01991. 2015. [3] John Lafferty, Andrew McCallum, Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289. 2001. [6] Erik F. Sang and Fien De Meulder. Introduction to the CoNLL-2003 shared task: Languageindependent named entity recognition. CoNLL. 2003.
Setup 1. Clone this repository: git clone https://github.gatech.edu/omscs6601/assignment_6.git 2. Navigate to the assignment_6/ directory 3. Activate your AI environment if you’re using Anaconda 4. Run the following command to install all requirements for this assignment: pip install -r requirements.txt Overview Hidden Markov Models are used extensively in Artificial Intelligence, Pattern Recognition, Computer Vision, and many other fields. If a system has unobservable (hidden) states and each state is independent of the prior, then we can create a model of that system using probability distributions over a sequence of observations. The idea is that we can provide this system with a series of observations to use to query what is the most likely sequence of states that generated these observations. The Files Submission All submissions will be via Gradescope. If you’re completing this assignment in Jupyter Notebook, you must run the notebook2script.py file to export your work to a python file. To generate your submission file, run the command python notebook2script.py submission: and your file will be created under the submission directory. Upload the resulting submission.py file to the Assignment 6A assignment on Gradescope for feedback. IMPORTANT: A total of 10 submissions is allowed for this assignment. Please use your submissions carefully and do not submit until you have thoroughly tested your code locally. If you’re at 9 submissions, use your tenth and last submission wisely. The submission marked as ‘Active’ in Gradescope will be the submission counted towards your grade. Resources 1. Canvas Lectures on Pattern Recognition Through Time (Lesson 8) 2. Challenge Questions on Piazza Local Testing If you are using submission.py to complete the assignment instead of the Jupyter Notebook, you can run the tests using: python hmm_submission_tests.py This will run all unit tests for the assignment, comment out the ones that aren’t related to your part (at the bottom of the file) if going step by step. The Assignment The goal of this assignment is to demonstrate the power of probabalistic models. You will build a word recognizer for American Sign Language (ASL) video sequences. In particular, this project employs hidden Markov models (HMM’s) to analyze a series of measurements taken from videos of American Sign Language (ASL) collected for research (see the RWTH-BOSTON-104 Database). In each video, an ASL signer is signing a meaningful sentence. In a typical ASL recognition system, you observe the XY coordinates of the speaker’s left hand, right hand, and nose for every frame. The following diagram shows how the positions of the left hand (Red), right hand (Blue), and nose (Green) change over time in video number #66. Saturation of colors represents time elapsed.In this assignment, for the sake of simplicity, you will only use the Y-coordinates of each hand to construct your HMM. In Part 1 you will build a one dimensional model, recognizing words based only on a series of right-hand Y coordinates; in Part 2 you will go multidimensional and utilize both hands. At this point, you will have two observed coordinates at each time step (frame) representing right hand & left hand Y positions. The words you will be recognizing are “BUY”, “HOUSE”, and “CAR”. These individual signs can be seen in the sign phrases from our dataset:JOHN CAN BUY HOUSEJOHN BUY CAR [FUTURE] Part 1a: Encoding the HMM [15 Points] Use the training samples from the table below. Provide the transition and prior probabilities as well as the emission parameters for all three words with accuracy to 3 decimal digits. Round the values to 3 decimal places thoughout entire assignment: – 0.1 stays 0.1 or 0.100 – 0.1234 rounds to 0.123 – 0.2345 rounds to 0.235 – 0.3456 rounds to 0.346 – 0.0123 rounds to 0.012 – 0.0125 rounds to 0.013 Those values can be hardcoded in your program. Don’t use round() from python. Word | Frames | Observed sequence | Initial State1 | Initial State2 | Initial State3 — | — | — | — | — | — BUY | 6 | 36, 44, 52, 56, 49, 44 | 36, 44 | 52, 56 | 49, 44 BUY | 8 | 42, 46, 54, 62, 68, 65, 60, 56 | 42, 46, 54 | 62, 68, 65 | 60, 56 BUY | 10 | 42, 40, 41, 43, 52, 55, 59, 60, 55, 47 | 42, 40, 41|43, 52, 55|59, 60, 55, 47 CAR | 10 | 47, 39, 32, 34, 36, 42, 42, 42, 34, 25|47, 39, 32|34, 36, 42|42, 42, 34, 25 CAR | 9 | 35, 35, 43, 46, 52, 52, 56, 49, 45|35, 35, 43|46, 52, 52|56, 49, 45 CAR | 8 | 28, 35, 46, 46, 48, 43, 43, 40|28, 35, 46|46, 48, 43|43, 40 HOUSE| 15 | 37, 36, 32, 26, 26, 25, 23, 22, 21, 39, 48, 60, 70, 74, 77|37, 36, 32, 26, 26|25, 23, 22, 21, 39|48, 60, 70, 74, 77 HOUSE| 15 | 50, 50, 49, 47, 39, 39, 38, 38, 50, 56, 61, 67, 67, 67, 67|50, 50, 49, 47, 39|39, 38, 38, 50, 56|61, 67, 67, 67, 67 HOUSE| 16 | 45, 43, 44, 43, 40, 35, 36, 37, 39, 45, 60, 68, 66, 72, 72, 75|45, 43, 44, 43, 40|35, 36, 37, 39, 45|60, 68, 66, 72, 72, 75 As shown in the diagram below, each one of the three words (BUY, CAR, and HOUSE) has exactly THREE hidden states in its HMM. All words must start from State 1 and can only transit to the next state or stay in the current one.Training sequences need to have 3 hidden states no matter what! If you follow the HMM training procedure described in Canvas, you might encounter a situation where a hidden state is squeezed out by an adjacent state; that is, a state might have its only observation moved to another state. In that situation, always keep at least one observation for that hidden state. Example: Assume you’ve reached a stage where the following is true: – State 1 has mean=53 & std=6 – State 2 has mean=37 & std=9 – State 3 has mean=70 & std=8 The next training sample has the following observed sequence: 45 45 34 | 30 30 25 36 52 | 62 69 74 and you are trying to adjust the location of state boundary between State 1 & 2. You first move it 1 step to the left since 34 is closer to State 2, and then you realize that 45 is still closer to State 2. If you follow the same routine, you will end up with no obvervation for State 1. In order to prevent this from happening, you have to stop at the last “45” and as a result leave the boundary as 45 | 45 34 30 30 25 36 52 | 62 69 74 Now you meet the ‘3 hidden states per sample’ requirement. Some hints/guidelines for training How should we compare if an observation if closer to one state or another? Check how many standard deviations away is the observation from the mean for each state. Example: Say 46 is the rightmost observation in S1. If we denote the mean and std of state i as μi,σi, then should we be comparing |46−μ1| / σ1 vs |46−μ2| / σ2 For HMM training, which side of the boundary should we check first while assigning observed sequence values to states? After computing the mean and std for each state, adjust the boundary between the states. Always start from the 1st element at the LEFT side of the boundary. If the LEFT element is closer to the next state, then move the boundary leftward. If the LEFT element should stay at the current state, then check the RIGHT element. This is just done to make sure that everyone gets the same results in the context of the assignment. Functions to complete: 1. part_1_a()Part 1b: Creating the Viterbi Trellis [40 Points] The goal here will be to use the HMM derived from Part 1a (states, prior probabilities, transition probabilities, and parameters of emission distribution) to build a Viterbi trellis. When provided with an evidence vector (list of observed right-hand Y coordinates), the function will return the most likely sequence of states that generated the evidence and the probabilty of that sequence being correct. For example, an evidence vector [36, 44, 52, 53, 49, 44] should output a sequence [‘B1’, … ‘B2’, … ‘B3’] If no sequence can be found, the algorithm should return one of the following tuples: (None, 0) (null), ([], 0) (empty list) or ([‘C1’, ‘C1’, … ‘C1’],0) (Or all being the first state of that letter) “No sequence can be found” means the probability reaches 0 midway. If you find an incomplete sequence with some probability, output that sequence with its probability. Functions to complete: 1. viterbi() Hint: In order to reconstruct your most-likely path after running Viterbi, you’ll need to keep track of a back-pointer at each state, which directs you to that state’s most-likely predecessor. You are asked to use the provided function gaussian_prob to compute emission probabilities. In a typical HMM model you have to convert the probability to log-base in order to prevent numerical underflow, but in this assignemnt we will only test your function against a rather short sequence of observations, so DO NOT convert the probability to logarithmic probability or you will fail on Gradescope. Gradescope: In the autograder, we will also test your code against other evidence_vectors.Part2a: Multidimensional Output Probabilities [6 Points] In Part 1a, we use only right-hand Y-axis coordinates as our feature, and now we are going to use both hands. Since ASL is two handed, using observations from both the right and left hands as features can increase the accuracy of our model when dealing with more complex sentences. Here you are given the transition probabilities and the emission parameters of left-hand Y-axis locations, following the same procedure conducted in Part 1a. One thing to notice is, in Part 1, the viterbi function is tested against single words. That is, the input evidence vector will not transit between different words. However, for Part 2, the input evidence vector can be either a single word, or a verb phrase such as “BUY CAR” and “BUY HOUSE”. Adjust the given transition probabilities to adapt to this fact. NOTE: Add NEW keys to the transition dictionary ONLY if there is a NON-ZERO transition probabilityBUY | State 1 | State 2 | State 3 — | — | — | — Mean | 108.200 | 78.670 | 64.182 Std | 17.314 | 1.886 | 5.573 CAR | State 1 | State 2 | State 3 — | — | — | — Mean | 56.300 | 37.110 | 50.000 Std | 10.659 | 4.306 | 7.826 HOUSE | State 1 | State 2 | State 3 — | — | — | — Mean | 53.600 | 37.168 | 74.176 Std | 7.392 | 8.875 | 8.347 Functions to complete: 1. part_2_a()Part 2b: Improving the Viterbi Trellis [39 Points] Modify the Viterbi trellis function to allow multiple observed values (Y location of right and left hands) for a state. The return format should be identical to Part 1b. Functions to complete: 1. multidimensional_viterbi() Gradescope: In the autograder, we will also test your code against other evidence_vectors.CONGRATULATIONS! You have just completed your final assignment for CS6601 Artificial Intelligence.
Introduction of assignment It is now possible to collect a large amount of data about personal movement using activity monitoring devices such as a Fitbit, Nike Fuelband, or Jawbone Up. These type of devices are part of the “quantified self” movement — a group of enthusiasts who take measurements about themselves regularly to improve their health, to find patterns in their behavior, or because they are tech geeks. But these data remain under-utilized both because the raw data are hard to obtain and there is a lack of statistical methods and software for processing and interpreting the data. Data The data for this assignment can be downloaded from the course web site: Dataset: Activity monitoring data [52K] The variables included in this dataset are: The dataset is stored in a comma-separated-value (CSV) file and there are a total of 17,568 observations in this dataset. Assignment This assignment will be described in multiple parts. You will need to write a report that answers the questions detailed below. Ultimately, you will need to complete the entire assignment in a single R markdown document that can be processed by knitr and be transformed into an HTML file. Throughout your report make sure you always include the code that you used to generate the output you present. When writing code chunks in the R markdown document, always use echo = TRUE so that someone else will be able to read the code. This assignment will be evaluated via peer assessment so it is essential that your peer evaluators be able to review the code for your analysis. For the plotting aspects of this assignment, feel free to use any plotting system in R (i.e., base, lattice, ggplot2) Fork/clone the GitHub repository created for this assignment. You will submit this assignment by pushing your completed files into your forked repository on GitHub. The assignment submission will consist of the URL to your GitHub repository and the SHA-1 commit ID for your repository state. NOTE: The GitHub repository also contains the dataset for the assignment so you do not have to download the data separately. Loading and preprocessing the data Show any code that is needed to 1. Load the data (i.e. read.csv()) 2. Process/transform the data (if necessary) into a format suitable for your analysis What is mean total number of steps taken per day? For this part of the assignment, you can ignore the missing values in the dataset. 1. Make a histogram of the total number of steps taken each day 2. Calculate and report the mean and median total number of steps taken per day What is the average daily activity pattern? 1. Make a time series plot (i.e. type = “l”) of the 5-minute interval (x-axis) and the average number of steps taken, averaged across all days (y-axis) 2. Which 5-minute interval, on average across all the days in the dataset, contains the maximum number of steps? Imputing missing values 1. Calculate and report the total number of missing values in the dataset (i.e. the total number of rows with NAs) 2. Devise a strategy for filling in all of the missing values in the dataset. The strategy does not need to be sophisticated. For example, you could use the mean/median for that day, or the mean for that 5-minute interval, etc. 3. Create a new dataset that is equal to the original dataset but with the missing data filled in. 4. Make a histogram of the total number of steps taken each day and Calculate and report the mean and median total number of steps taken per day. Do these values differ from the estimates from the first part of the assignment? What is the impact of imputing missing data on the estimates of the total daily number of steps? Are there differences in activity patterns between weekdays and weekends? 2. Make a panel plot containing a time series plot (i.e. type = “l”) of the 5-minute interval (x-axis) and the average number of steps taken, averaged across all weekday days or weekend days (y-axis). The plot should look something like the following, which was creating using simulated data:Your plot will look different from the one above because you will be using the activity monitor data. Note that the above plot was made using the lattice system but you can make the same version of the plot using any plotting system you choose. Submitting the Assignment To submit the assignment: 1. Commit the your completed PA1_template.Rmd file to the master branch of your git repository (you should already be on the master branch unless you created new ones) 2. Commit your PA1_template.md and PA1_template.html files produced by processing your R markdown file with knit2html() function in R (from the knitr package) 3. If your document has figures included (it should) then they should have been placed in the figures/ directory by default (unless you overrided the default). Add and commit the figures/ directory to yoru git repository. 4. Push your master branch to GitHub. 5. Submit the URL to your GitHub repository for this assignment on the course web site. In addition to submitting the URL for your GitHub repository, you will need to submit the 40 character SHA-1 hash (as string of numbers from 0-9 and letters from a-f) that identifies the repository commit that contains the version of the files you want to submit. You can do this in GitHub by doing the following 1. Going to your GitHub repository web page for this assignment 2. Click on the “?? commits” link where ?? is the number of commits you have in the repository. For example, if you made a total of 10 commits to this repository, the link should say “10 commits”. 3. You will see a list of commits that you have made to this repository. The most recent commit is at the very top. If this represents the version of the files you want to submit, then just click the “copy to clipboard” button on the right hand side that should appear when you hover over the SHA-1 hash. Paste this SHA-1 hash into the course web site when you submit your assignment. If you don’t want to use the most recent commit, then go down and find the commit you want and copy the SHA-1 hash.
Expectation Maximization – Assignment 5 – CS6601Setup Clone this repository: git clone https://github.gatech.edu/omscs6601/assignment_5.git Please use the same environment from previous assignments by running conda activate ai_env Jupyter Notebook: You will be using jupyter notebook to complete this assignment. To open the jupyter notebook, navigate to your assignment folder, (activate your environment if you have/using one), and run jupyter notebook. Project description and all of the functions required to implement you will find in the solution.ipynb file. ATTENTION: You are free to add additional cells for debugging your implementation, however, please don’t write any inline code in the cells with function declarations, only edit the section inside the function, which has comments like: # TODO: finish this function. Grading The grade you receive for the assignment will be distributed as follows: 1. k-Means Clustering (19 points) 2. Gaussian Mixture Model (48 points) 3. Model Performance Improvements (20 points) 4. Bayesian Information Criterion (12 points) 5. Return your name (1 point) Submission The tests for the assignment are provided in mixture_tests.py. All the tests are already embedded into the respective ipython notebook cells, so they will run automatically whenever you run the cells with your code. Local tests are sufficient for verifying the correctness of your implementation. The tests on Gradescope will be similar to the ones provided here. To get the submission file, make sure to save your notebook and run: python notebook2script.py submit Once the execution is complete, open autogenerated submit/submission.py and verify that it contains all of the imports, functions, and classes you are required to implement. Only then proceed to the Gradescope for submission. In your Gradescope submission history, you can mark certain submissions as Active. Please ensure this is your best submission. Do NOT erase the #export at the top of any cells as it is used by notebook2script.py to extract cells for submission. You will be allowed 3 submissions every 3 hours on gradescope. Make sure you test everything before submitting it. The code will be allowed to run for not more than 40 minutes per submission. In order for the code to run quickly, make sure to vectorize the code (more on this in the notebook itself). Resources 1. Canvas lectures on Unsupervised Learning (Lesson 7) 2. The gaussians.pdf in the read/ folder will introduce you to multivariate normal distributions. 3. A youtube video by Alexander Ihler, on multivariate EM algorithm details: https://www.youtube.com/watch?v=qMTuMa86NzU 4. The em.pdf chapter in the read/ folder. This will be especially useful for Part 2 of the assignment.
Objectives ● Develop an application based on requirements. ● Use JUnit for testing. In this lab, you will model and solve simple DC circuits composed of any number of resistors and voltage sources. Unlike previous labs, you are not given the design for this application. It is up to you to decide what classes, interfaces, methods, etc. that you will need. The one exception is that you must have a class called UserMain that has a main() method that reads and interprets input from stdin (by default, the keyboard).Overview An electric circuit will be described by the user. Each line will describe either a Resistor or a DC Voltage source or be a single word command. The format for describing (for example) a 5.2 Ohm resistor connected between nodes 2 and 3 is: r 2 3 5.2 The format for describing a 6.5 Volt source connected between nodes 1 and 2 (where the positive side of the source is connected to node 1) is: v 1 2 6.5 A complete circuit could be described as follows: v 1 0 2.0 r 1 2 0.25 v 2 0 3 r 2 3 0.5 r 3 0 1.0 end To be correct, a circuit with n nodes must name the nodes 0, 1,…n-1. The order in which the components are described does not matter. For non-polarized components (such as a resistor), the order in which the nodes are named does not matter. For example, r 1 2 0.25 is equivalent to: r 2 1 0.2 For polarized components (such as a voltage source), the order does matter. Thus: v 1 0 2.0 is equivalent to: v 0 1 -2.0 In addition to lines describing the components of a circuit, there are 2 other single word commands that can be entered: spice and end. The end is the simplest to understand and implement. When the end command is entered, the program should print All Done and terminate. The spice command should print the spice description of the circuit entered so far. In the spice description, uppercase letters are used, components are numbered sequentially and DC is used in the description of voltage sources. An example session follows (the lines in bold denote output from the program; the non-bold lines are input): v 1 0 2.0 r 1 2 0.25 v 2 0 3 r 2 3 0.5 r 3 0 1.0 spice V1 1 0 DC 2.0 R1 1 2 0.25 V2 2 0 DC 3.0 R2 2 3 0.5 R3 3 0 1.0 end All Done Source Code No source code template is given for this lab. You will have to write the code from scratch. Step 1: Create a Netbeans Project and implement the end command 1. Create a Netbeans project called AnalogCircuit which should be placed in a folder called lab6 (all lowercase and no spaces). The lab6 folder should itself be in your coe318 folder. 2. Create a class UserMain with a main method that reads stdin and interprets the end command. This and all classes should be in a package called coe318.lab6. Step 2: Interpret the circuit and Implement the spice command You need to define classes that will allow you to model the circuit. Include javadoc comments for all public methods, classes, interfaces and constructors. Once you can interpret circuit components, you should be able to implement the spice command. Step 3: Write Unit Tests for one of the classes Write JUnit tests for testing at least two methods of one of the classes that you write. Step 4: Submit your lab Please zip up your NetBeans project containing all source files and submit to the respective assignment folder on D2L.
Objectives ● Implement a Card class. ● Implement a CardPile class. ● Implement a SimpleUI class. ● Fix the BlackjackGame class. ● Use an ArrayList ● Perform user I/O. Duration: two weeks. Grading Scheme: 50% submitted source code 20% in-class demonstration and questions (during week 8 lab hours) 25% in-class quiz – Held during the first 5 mins of the lab class (during week 5 lab hours) 5% attendance Overview Blackjack is the most popular casino gambling game in the world. (Note: the rules of the game favor the casino. The Casino is guaranteed to win in the long run.) Here’s how it works: 1. Both you and the House (the Casino) are dealt two cards: one is face up and the other face down. So you can see only one of the House’s cards and it can see only one of yours. But both you and the House can discreetly peek at your face down cards. 2. Each card has a score as follows: ● An Ace has a score of 1. (This differs from real Blackjack where the Ace can have a score of either 1 or 11 at the player’s discretion. The simplified version for this lab is easier to program.) ● A Jack, Queen or King has a score of 10. ● All other cards have a score equal to their rank. (For example, the 4 of Hearts or the 4 of any suit have a rank of 4 and a score of 4.) 3. The House will obtain additional cards until its score is 17 or more. 4. You are asked if you want another card. If you answer yes, you get another face down card and you will be asked again. This continues until you say “no”. This ends the game. 5. All cards are now turned face-up and the scores of you and the House are calculated. ● You lose if your score is more than 21 (no matter what the House’s score is). ● You lose if your score is the same as the House’s. ● You win if: o You don’t go over 21 and the House does go over 21 o Both your scores are 21 or under and your score is more than the House’s. The Card Class The Card class will consist of instance variables, a constructor and the methods. The template contains javadocs for all the methods. You should generate the html representation of the class to have an easier representation of the class’s API (Application Programmer Interface). Many of the methods are only stubs and you have to modify them so that they implement the API. The template will compile and it has a main method that will run but it produces the wrong output. Source Code Card.java, CardPile.java, BlackJackGame.java, UserInterface.java and SimpleUI.java classes are provided with the lab. More details about these classes are in the instructions below. Step 1: Create a Netbeans Project and Card class 1. Create a Netbeans project called Blackjack. 2. Create a Java file (class library type) called Card with package coe318.lab5. (All java files in this lab should have that package declaration.) 3. Determine your instance variables and implement the constructor. 4. Implement the other methods. 5. Important: Do not continue to the next class until this class works! Step 2: Implement the remaining classes You should get the CardPile class to work before proceeding. (It has its own main method.) You next have to create the BlackjackGame and SimpleUI classes starting with the templates provided. You also have to create an interface (UserInterface) copying the code given in D2L. To create an interface in Netbeans, create a new file and have an interface (not a class) created. We have not covered interfaces yet in lectures. However, the only thing you need to know for now is that this file is essential and must not be modified. Note: All three of these templates have to be loaded in order for them to compile without error. Additional Notes 1. The Card class compareTo(Card c) method should return a negative, zero or positive value depending on whether “this” is less than, equal to or greater than the other card. For 2 cards of unequal rank, the one with the higher rank is “bigger”. If the ranks are the same, the suit is considered; the suit orders (from lowest to highest) are Clubs, Diamonds, Hearts, Spades. 2. The Card equals(Card c) method should only return true if the cards have the same suit and rank. Sample Gaming Sessions The following are 2 sample sessions. In one the House wins, in the other you win. Note: The format of the output is not defined. Within SimpleUI you can format the output of display(), hitMe() and gameOver()any way you want. House holds: ? 7 of Hearts You hold: Queen of Hearts Jack of Clubs House holds: ? 7 of Hearts 6 of Spades You hold: Queen of Hearts Jack of Clubs Another card? n House holds: ? 7 of Hearts 6 of Spades King of Spades You hold: Queen of Hearts Jack of Clubs Game over House holds: Ace of Diamonds 7 of Hearts 6 of Spades King of Spades You hold: Queen of Hearts Jack of Clubs Your score: 20, House score: 24 You win House holds: ? 4 of Clubs You hold: King of Spades 3 of Spades House holds: ? 4 of Clubs Ace of Diamonds You hold: King of Spades 3 of Spades Another card? y House holds: ? 4 of Clubs Ace of Diamonds You hold: King of Spades 3 of Spades 9 of Clubs House holds: ? 4 of Clubs Ace of Diamonds Queen of Clubs You hold: King of Spades 3 of Spades 9 of Clubs Another card? n Game over House holds: Jack of Spades 4 of Clubs Ace of Diamonds Queen of Clubs You hold: King of Spades 3 of Spades 9 of Clubs Your score: 22, House score: 25 The House wins Step 4: Submit your lab Please zip up your NetBeans project containing all source files and submit to the respective assignment folder on D2L.
