Option 1:
hex2bin: takes each hexadecimal address and converts it to an equivalent binary value. You can extend the number of bits to 32 bits to simplify your conversion but this is not a requirement. As an example, if the hex input is “f429a”, the output of hex2bin would be “00000000000011110100001010011010”( with padding to 32-bit) or “11110100001010011010” (without padding).
To help you start this assignment, I am providing you with a starter code that has all the libraries that you can import (do not import any more libraries) and binLookup. Your hex2bin function should call binLookup to convert each hex digit to an equivalent binary value.
— copy the following code to your traceProcP1.hs
import System.IO
import Data.List
import System.Environment
binLookup :: Char -> String
binLookup ‘0’ = “0000”
binLookup ‘1’ = “0001”
binLookup ‘2’ = “0010”
binLookup ‘3’ = “0011”
binLookup ‘4’ = “0100”
binLookup ‘5’ = “0101”
binLookup ‘6’ = “0110”
binLookup ‘7’ = “0111”
binLookup ‘8’ = “1000”
binLookup ‘9’ = “1001”
binLookup ‘a’ = “1010”
binLookup ‘b’ = “1011”
binLookup ‘c’ = “1100”
binLookup ‘d’ = “1101”
binLookup ‘e’ = “1110”
binLookup ‘f’ = “1111”
binLookup j = error “Your input is not a hex digit”
— end your copy here
bin2dec: takes each output of hex2bin and converts it to a decimal value. For example, if the output of hex2bin is “00000000000011110100001010011010”, the output of bin2dec is “1000090”. Your function should calculate this value by: 2^1 + 2^3 + 2^4 + 2^7 + 2^9 + 2^14 +2^16 + 2^17 + 2^18 + 2^19 (these are the bit positions with the value of 1).
=================================
Option 2:
hex2dec: takes each hexadecimal address and converts it to an equivalent decimal value. You can modify the starter code in Option 1 to create a look-up function that converts hexadecimal to decimal.
=================================
Once you have the addresses in decimal values, you can compute the number of occurrences for each address. You need to store the information using the following type:
[(Int, Int)] -> a list of tuples where the first element of each tuple is the number of accesses and the second element is the address in decimal. Thus, the addresses should all be unique (since all duplicated addresses are accounted for in the number of accesses element).
genOutput: takes the list of tuples and produces the output file (spice.dout), where the first column contains the numbers of accesses to address; the second column contains the decimal addresses. A tab separates the two columns. Your output is sorted based on the addresses (from the lowest address to the highest address). The provided oracle file Download oracle fileillustrates the required format.
main: is the main body of the program. It invokes all the necessary functions to complete the trace processing requirements. Compare your output file (spice.dout) to the oracle file for this part using diff -w command; it should report no differences.
Note that your program for part 1 should be named “traceProcP1.hs”. It will take two command-line arguments. The first argument is the name of the input file (e.g., spice.din), and the second argument is the name of the output file (e.g., spice.dout).
Part II – Page-based trace processing (32 points)
Using byte-addressable addresses is the finest granularity that we can observe memory accesses. However, we may also notice that some addresses only have very few accesses. Data migration from storage (solid-state drives or hard drives) to main memory occurs at a page granularity in a typical computer system. To better explain the paging concept, imagine that you have a long scroll that contains 1,000,000 characters. Let’s say you want to access character 567,489; finding this character in this long scroll can be quite an ordeal. Human overcomes this ordeal by packaging information into books. For example, we can partition this scroll into a book in which each page is containing 10,000 characters. As such, the book would have 1,000,000 / 10,000 or 100 pages. To find character 567,489, we need to find the page number and the offset within that page. The page number is 567,489 / 10,000 (or 56) and the page-offset is 567,489 % 10,000 (or 7,489).
Now, let’s think about this problem from the data migration perspective. In a 32-bit memory system, your address is from 0x00000000 to 0xFFFFFFFF or 2^32 addresses. Finding an address in this vast space requires partitioning the space into pages. Furthermore, partitioning also helps with lazy data movement; i.e., the system only needs to move pages containing the information currently needed into memory instead of moving the entire address space. Let’s assume that we have a page size of 2,048 bytes or 2^11. Given an address in hex (e.g., 0x2f2480a), we would find the page number by shifting the address to the right by 11 bits. Thus, in this example, our address in binary is 0000 0010 1111 0010 0100 1000 0000 1010. Shifting right by 11 bits would result in 0000 0000 0000 0101 1110 0100 1001 or 0x0005e49.
For part two, we will assume that our page size is 2,048 bytes (again 2^11). Your task is to produce an output file (spice_page.dout) that contains the number of accesses to each page. To do so, you need to modify your program in Part 1 to convert each address in spice.din Download spice.dinto its corresponding page number (i.e., by shifting right by 11 bits) and then report each page’s access. You also need to filter out any page that has 99 accesses or fewer. Your output is sorted based on the page numbers (from the lowest page number to the highest page number). Again, do not import any more libraries. Compare spice_page.dout to the oracle file Download oracle filefor this part using diff -w command; it should report no differences.
