# HW4: Bitcoin Miner

Due: Tue, 2022/5/10 23:59

[toc]

# Problem Description
Slides: https://docs.google.com/presentation/d/1d_Xi9UzD6BI3RHbO48W4R02h_6w_7locehqUPmDTzPk/edit?usp=sharing

In this homework, we provide you the sequential (CPU) code of the bitcoin miner. You are asked to **parallelize it with CUDA**. You may use any techniques that you’ve learned in this class!

## Input Format
* First line of the input is an integer N represent number of blocks to solve.
* Follow by N block of below data
| Data | Description |
| ---------------------------------------------------------------- | --------------------------------------- |
| 20000000 | Version |
| 0000000000000000003348540cbfc68b70825e7abcd5a83a48a5f87fa7f1aace | Previous block hash |
| 5ac22f8b | Timestamp |
| 17502ab7 | Nbits (difficulty) |
| 2094 | Number of transactions |
| c6574adb277efbfb972658ab78b1277707a967076cfc90d6af800cd8a915396d | Transactions (2094 line of hash values like this) |

## Output Format
* First line of your output is an integer N represent number of blocks.
* Follow by N line of nounce value.
* You can found out example in `hades:/home/ipc22/share/hw4/testcases/*.out`

## Compilation
**We use Hades server for this homework.**

We use `Makefile` to build your code. The default Makefile for this homework is provided at `/home/ipc22/share/hw4/sample/Makefile`.
If you wish to change the compilation flags, include `Makefile` in your submission.

To use Makefile to build your code, make sure `Makefile`, `hw4.cu`, `sha256.cu`, `sha256.h` are in the working directory, then run `make` on the command line and it will build `hw4`
for you. To remove the built files, run `make clean`.

We will compile your code with the command `make`.

## Execution

Your code will be executed with a command equalviant to:

~~~
srun -p ipc22 -N1 -n1 -c1 --gres=gpu:1 ./hw4 caseXX.in caseXX.out
~~~

The time limit for each test case is 240 seconds.

# Report

Answer the following questions, in either English or Traditional Chinese.

1. Your implementation
1. The parallelization and optimization techniques you used in your solution
1. Experiments of various combinations of the number of blocks & threads (at least 8 combinations) and plot them with the figures
1. Describe the details if you use advanced CUDA skills
1. If you optimize the other parts of your source codes, please demonstrate your experimental results. We REQUIRE you to justify your solutions so that we can give you credits.
1. (Optional) Any suggestions or feedback for the homework are welcome.

# Submission

Upload these files to EEClass:

* `hw4.cu`, `sha256.cu`, `sha256.h` -- the source code of your implementation.
* `Makefile` -- optional. Submit this file if you want to change the build command.
* `report.pdf` -- your report.

Please follow the naming listed above carefully. Failing to adhere to the names
above will result to points deduction. Here are a few bad examples: `hw4.CU`,
`HW4.cu`, `report.docx`, `report.pages` `Makefile.mak`.

# Grading

1. (40%) Correctness. Propotional to the number of test cases solved.
2. (30%) Performance. Based on the total time you solve all the test cases. For a
failed test case, 300 seconds is added to your total time.
3. (30%) Report.

# Appendix

Please note that this spec, the sample test cases and programs might contain bugs.
If you spotted one and are unsure about it, please ask on eeclass.

## Sequential (CPU) Version

The reference C++ implementation is under `/home/ipc22/share/hw4/sample/`. The refernce code follows the same input/output format as your homework.

## Sample Testcases

The sample test cases are located at `/home/ipc22/share/hw4/testcases`.

## Output validation

`/home/ipc22/share/hw4/validation` can be used to check yout answer.

For example:
~~~
/home/ipc22/share/hw4/validation /home/ipc22/share/hw4/testcases/case00.in your_case00.out
~~~

You may also use python script to check your code
~~~
python3 /home/ipc22/ta/hw4/runner.py caseXX ./hw4
~~~

## Judge

The `hw4-judge` command can be used to automatically judge your code against
all sample test cases, it also submits your execution time to the scoreboard
so you can compare your performance with others.

Scoreboard: https://apollo.cs.nthu.edu.tw/ipc22/scoreboard/hw4/

To use it, run `hw4-judge` in the directory that contains your code `hw4.cu`, `sha256.cu`, `sha256.h`.
It will automatically search for `Makefile` and use it to compile your code,
or fallback to the TA provided `/home/ipc22/share/hw4/sample/Makefile` otherwise.
If code compiliation is successful, it will then run all the sample test cases,
show you the results as well as update the scoreboard.

> Note: `hw4-judge` and the scoreboard has nothing to do with grading.
> Only the code submitted to iLMS is considered for grading purposes.

Type `hw4-judge --help` to see a list of supported options.

### Judge Verdict Table

| Verdict | Explaination |
|--|--|
| internal error | there is a bug in the judge |
| time limit exceeded+ | execution time > time limit + 10 seconds |
| time limit exceeded | execution time > time limit |
| runtime error | your program didn't return 0 or is terminated by a signal |
| no output | your program did not produce an output file |
| wrong answer | your output is incorrect |
| accepted | you passed the test case |