SSE3054: Multicore Systems (Spring 2017)

[Programing Assignment]

3D Game of Life

3D Game of Life source code (Sequential)

3D Game of Life source code (Pthread)

Example ver.01

Example ver.02

Test map size 100 ver.01

Test map size 200 ver.01

Test map size 300 ver.01

Skeleton code about Pthread is uploaded. (NEW life.c setup.h game.c game.h input.life)
Any other codes used at sequential project are same. So, copy that codes.
Rule is same. You can only change game.c game.h Makefile(can add new files) README.
Finally, when you submit your Pthread code, put all your source code in NAME studentID directory. For example,

$ mkdir 2012345678
$ mv or cp * (all "your" source codes like game.c, game.h, Makefile, README, etc.) 2012345678
$ tar cvf 2012345678.tar 2012345678

Pthread 프로젝트에서 사용될 스켈레톤 코드를 업데이트 하였습니다. (NEW life.c setup.h game.c game.h input.life)
시퀀셜 프로젝트에서 사용된 나머지 코드는 동일하게 사용 가능하므로 그대로 복사하셔서 사용하시면 됩니다.
프로젝트 룰은 동일합니다. game.c game.h Makefile(새로운 파일 추가 가능) README를 압축하셔서 제출하시면 됩니다.
추가로, Pthread 프로젝트부터 제출하실 때, 모든 프로젝트 파일들을 본인의 학번과 동일한 이름의
디렉토리에 넣어서 제출해 주시기 바랍니다. 위의 예시를 참고 바랍니다.

Total example input and output file is uploaded.
Grading test environment can be changed. Keep in mind.
This tests just only aims to check for correct answers.

예시 Input, Output 파일들을 전부 업로드 하였습니다.
하지만, 점수를 결정하는 실행 환경은 달라질 수 있음을 숙지하시기 바랍니다.
업로드 된 파일들은 자신이 만든 코드가 옳게 동작하는지 확인하는 용도입니다.


[Test Result]

Sequential Test Result (updated at 4/24)

Modified project file should be submitted to (Delay) Sequential project in Icampus assignment.

수정된 프로젝트 파일은 Icampus 과제란에 새로 개설된 (Delay) Sequential project에 제출해 주시기 바랍니다.

Sequential test result is uploaded.
map_size is 300 and iteration count is 50.
Time out is exceeding 1 hour running time(Iteration 50, 100 each).
Your score about time out test case will be zero.
Other test cases have lower map size and iteration count.
However, if your running time also exceed 1 hour when execute these cases, your score about that inputs also will be zero.
Invalid outputs is wrong, no, or additional outputs.
In that case, your project code also generate wrong outputs when execute other test cases, so check your code one more time.

If you have any questions about result, please email me.

However, "Compile error" or "Not submit" result students should check your submission form and compile your submission code with uploaded skeleton code (life.c setup.h lcgrand.c lcgrand.h list.c list.h) in Ubuntu before email me.

시퀀셜 테스트 결과를 업로드 하였습니다.
Time out은 제한시간인 1시간 동안 결과가 나오지 않은 학생들입니다(Iteration 50, 100 각각 1시간).
Time out의 경우, 해당 Input에 대한 점수는 0점 처리됩니다.
나머지 test의 경우 map_size와 iteration 횟수는 줄어들 예정이지만, 해당 Input들에서도 Time out이 나올 경우, 해당 Input들에 대해서도 0점 처리됨을 감안해 주시기 바랍니다.
Invalid outputs는 결과 출력을 제대로 수행하지 못한 것입니다.
해당 경우, 다른 테스트에 대해서도 잘못된 결과 출력을 할 가능성이 높으므로, 제출한 파일을 다시 한 번 확인 바랍니다.

결과에 이상이 있으시면 제게 메일을 보내주시기 바랍니다.

다만, 제출한 학생들 중 제출하였지만 Compile error 혹은 Not submit으로 체크되어 있는 학생들은 다시 한번 제출한 파일이 형식에 맞는지, 아니면 본인이 제출한 파일을 다운로드 한 뒤 제공된 스켈레톤 코드에서 life.c setup.h lcgrand.c lcgrand.h list.c list.h를 복사한 뒤 우분투 환경에서 컴파일을 진행해 보신 후에, 이상이 있으시면 제게 메일을 주시기 바랍니다.


[Server Information]

IP ADDRESS: 4/26 open

CPU: Intel(R) Xeon(R) CPU E7-8890 v4

L3 Shared Cache size: 61.44MB

Memory size: Larger than 250G

In sequential test environment, maximum 30min ~ 1hour(can be changed according to submit student number) time
will be given to your code.
If your sequential project run more than that maximum time, your test will be finished by force.
In this case, because your output files normally cannot be generated, your point will be degraded about that input.
This time is not total stage time, but main function finish time.

시퀀셜 테스트 환경에서, 제출한 학생의 인원 수에 따라 최대 실행 시간을 30분~1시간 정도로 부여할 예정입니다.
만약 해당 시간까지 프로젝트 실행이 종료되지 않을 경우, 실행 중인 프로세스를 강제로 종료시킬 예정입니다.
이 경우에, 아웃풋 파일이 정상적으로 출력되지 않을 것이며, 해당 인풋에 대한 감점이 있을 것입니다.
프로젝트 프로세스의 수행 시간은 main 함수 전체 시간을 기준으로 합니다.


[IMPORTANT RULE CHANGES]

1) In angel stage, previous rule is angle scope is equal to devil count.
This rule is changed.
In angel stage, angle scope is equal to X, int X = (devil count / (5 * map_size * map_size)).
In this rule, angel scope value can be 0.
So, angel scope is set to X, int X = (angel move count / 2) when scope < X.
Angel scope can change in each step.

기존의 룰에서는 angel scope의 값이 현재 존재하는 devil의 수와 동일하였지만
바뀐 룰에서는 devil 수 / (5 * map_size * map_size)으로 입력됩니다.
angel scope의 자료형은 integer 형이므로, scope의 값이 0이 되는 경우가 발생할 수 있습니다.
X = angel이 한번에 이동할 수 있는 값 / 2 라고 할 때, X > scope일 경우 scope = X로 설정하시면 됩니다.
Angel scope의 값은 매 스텝마다 변경되므로 주의해서 프로젝트를 진행해 주시기 바랍니다.

2) In devil stage, previous rule is all devil has different move direction.
This rule is changed.
In devil stage, you should get just once random value about move.
For example, x = uniform(0, 2, SEED_MOV), y = uniform(0, 2, SEED_MOV), z = uniform(0, 2, SEED_MOV)
is performed JUST once, and ALL DEVILs move SAME direction.

Pthread 코드에서 진행해 본 결과,
devil마다 다른 랜덤 값으로 이동시키는 경우 싱크가 맞지 않는 결과를 확인하였습니다.
따라서, devil stage에서 단 한 번의 devil 이동에 대한 랜덤 값을 얻으신 후,
모든 Devil을 동일한 방향으로 이동시켜주시기 바랍니다. 맵을 벗어나는 devil에 대해서는
기존의 룰을 그대로 적용하시면 됩니다.


[Problems of code]

1) After 100,000,000 iteration tests, uniform function executed at 32bit Ubuntu 14.04
makes some different value ( + - 1 ) after 500,000 iterations comparing with 64bit Ubuntu 16.04.
However, some students already finish project1 and
I referred to use 64bit Ubuntu 16.04 or 14.04 when describe about project.
If you have only 32bit machine, check your code by using newly updated example version 2.
After that, test your code at semi-building 400222.
I already notify semiconductor department office, so multicore students can use that computer room.
example version 2 does not make problem caused by 32bit machine.

QnA시간에 언급된 uniform 함수에 대하여 우분투 14.04 32비트 머신과 16.04 64비트 머신에서 1~10 랜덤시드에 대하여
1억번의 uniform 함수 실행 결과 50만번 이후로 출력 값이 간헐적으로 1씩 차이가 나는 현상을 발견하였습니다.
하지만 이미 프로젝트를 종료한 학생들이 존재하며, 프로젝트 설명에서 프로젝트는
우분투 64비트 16.04 혹은 14.04에서 진행할 것을 언급하였습니다.
만약 자신이 32비트 머신만을 소유하고 계시다면, 새로 업로드한 example ver2로 먼저 확인을 하신 뒤에,
test case들은 반도체관 400222에서 확인할 것을 부탁드립니다.
반도체 행정실에 이미 허락을 맡아놨으니 프로젝트 관련하여 자유롭게 사용하실 수 있습니다.
example ver2는 32비트 머신으로 인한 문제는 발생하지 않을 겁니다.

2) Provided list.c file has a problem.
b->next = b_next should be changed to b->next = a_next in list_swap funtion, line 498.

제공된 list.c에서 문제를 발견하였습니다.
498번 라인의 list_swap 함수에서 b->next = b_next를 b->next = a_next로 수정해주시기 바랍니다.


[Assignment Due]

[4/10 ~ 4/20] Sequential project
[4/21 ~ 5/06] Pthread project
[5/07 ~ 5/13] OpenMP exercise
[5/14 ~ 5/24] OpenMP project
[5/25 ~ 5/31] MPI exercise
[6/01 ~ 6/11] MPI project

Assignment due is changed. Please keep in mind.
중간고사와 겹친다는 학생들의 요청으로, Pthread project 기간이 연장되었습니다.


[Answers about question]

[Initialize resources]

1) In Final_pos.txt, you should sort devil coordinates in x, y, z sequence.
For example, (27, 45, 10), (110, 5, 50), (20, 49, 38), (11, 30, 169), (20, 70, 21)
=> (11, 30, 169), (20, 49, 38), (20, 70, 21), (27, 45, 10), (110, 5, 50)

Final_pos.txt를 작성하실 때, devil의 좌표를 x, y, z 순서대로 정렬을 하여 출력해 주셔야 합니다.
위의 예시를 참고해 주세요.

2) In initializing map, you can use any data structure such as array, list(use list.c and list.h, but not mandatory), etc.
However, you should determine logical coordinate (0,0,0) to (map_size-1, map_size-1, map_size-1).
When you initialize map by using uniform function, first return value must put your logical coordinate (0,0,0)
and second return value must put logical coordinate (0,0,1) in sequence.
In printing your map, you should print logical coordinate in sequence (0,0,0), (0,0,1), ...

맵 초기화에 대해 질문이 많습니다. 맵은 여러분이 사용하고자 하는 자료구조를 마음대로 사용하시면 됩니다.
list.c와 list.h의 경우 여러분이 리스트를 구현하는 부담을 덜어드리고자 첨부한 것입니다. 사용하는 것이 의무는 아닙니다.
단, 여러분의 자료구조에서 논리적인 좌표는 반드시 정해져야 하고 이는 고정되어야 합니다.
즉, (0,0,0)에서부터 (map_size-1, map_size-1, map_size-1) 까지가 맵에서 정해져야 합니다.
맵 초기화 시, uniform 함수로 얻어지는 값들을 차례대로 (0,0,0), (0,0,1), ...에 넣어주시면 됩니다.
또한 맵 출력 시, (0,0,0), (0,0,1), ...의 순서대로 출력해주시면 됩니다.

3) In initializing map, you should one one state change to PLAGUE occupied by devil.
In other words, when you initialze map, devil is positioned at one cell and that cell state moves to PLAGUE state. However, in initializing map, devil doesn't copy.

맵 초기화 시, devil의 위치를 정한 뒤, 해당 셀을 PLAGUE 상태로 바꿔주셔야 합니다. 즉, 맵 초기화 부분에서는 devil stage의 devil이 복제되는 부분만 제외하고 진행해 주시면 됩니다.
그 뒤에 devil stage에 진입한 후, devil move -> state change to PLAUGE -> devil copy를 진행해 주시면 됩니다.

4) In 16 page of project slide, 4) and 5) Generate ~~ means print initial devil, angel, and map status.
Just that.

프로젝트 슬라이드 16페이지에서 4)와 5)번 항목의 Generate ~~는 Initial_pos.txt, Initial_map.txt를 생성하라는 의미입니다. 다른 작업을 요하는 것이 아닙니다.

[Devil stage]

1) In devil stage, program sequence is

  • devil gen or move (If multiple cells in one cell, they are merged)
  • Make cell state to PLAGUE
  • Devil copy

If, in devil copy sequence, devil is generated one cell which is occupied by other devil,
they are NOT merged. Merge sequence is progressed at 1st sequence in devil stage.

Devil stage에서의 프로그램 진행 시퀀스는 다음과 같습니다.

  • Devil 생성 혹은 이동 (이 때 다수의 Devil이 하나의 Cell로 중첩될 시, 하나의 Devil만 남기고 전부 제거해 주시면 됩니다.)
  • Cell의 상태를 PLAGUE 상태로 수정
  • Devil 복제

여기서, Devil stage의 마지막 시퀀스인 Devil 복제 부분에서 생성된 Devil이 만약 다른 Devil이 존재하는 Cell에 생성될 경우, 해당 Step에서는 Devil을 제거하실 필요가 없습니다. 다음 Step에서 제거해 주시면 됩니다.

[Live and dead stage]

[Plague stage]

[Angel stage]

[Free resources]

1) Please write your code if you use memory allocation like malloc, then you must free memory resource.
In your computer, this may not cause fault, however, in our environment, this can cause fault.
This bad result is taken to you. Keep in mind. Memory management.

메모리 할당을 하는 경우 프로그램 종료 시 반드시 할당 받은 메모리를 해제해 주시기 바랍니다.
단일 프로그램을 수행시키는 여러분의 환경의 경우에는 이것이 Fault를 발생시키지 않을 수도 있지만,
채점을 하는 서버의 경우, 이것이 Fault를 발생시킬 가능성이 있습니다.
해당 문제가 발생한 경우, 코드가 제대로 수행되지 않은 것으로 가정, 해당 코드는 0점 처리됩니다.
물론, 문제가 발생하지 않는다면 여러분이 받는 불이익은 없지만, 만약을 대비하여 공지합니다.

[ETC]

1) Submitting README file is changed to mandatory for professor hope.
README file must contain below contents
a. Data structures which is used by you. (map, devil, etc.)
b. Algorithms which is used by you
c. Description of how to reduce your execution time by using your data structure and algorithm
d. Contact(email address or cell phone number)
Please write README file at ubuntu environment. File name is just "README" (NOT "README.txt")
If you submit without README file, that project file will be invalidated.

README 파일이 교수님의 요청에 의해서 의무적으로 제출하는 것으로 변경되었습니다.
README 파일은 다음의 내용을 포함해야 합니다.
a. 사용하신 자료구조 (map, devil 등에 관한 자료구조)
b. 사용하신 알고리즘
c. 자료구조와 알고리즘을 사용하여 어떻게 실행시간을 단축시켰나 설명
d. 연락처(이메일 주소 혹은 휴대폰 번호)
README는 편하신 언어(한글 혹은 영어만 가능)로 작성해 주시면 됩니다.
README는 우분투 환경에서 에디터(vi, vim, etc.)로 작성해 주시면 되며,
파일 이름은 "README"로만 해주시기 바랍니다. ("README.txt" 이런 것을 금지한다는 뜻입니다.)
README 파일을 포함하여 제출하지 않을 시, 제출된 프로젝트 파일은 무효로 간주됩니다.

2) When you submit your project in iCampus, your filename MUST "studentID.tar".
I will check all of your project by using shell script.
So, if you don't follow submit rule, your score can be 0.

Submit Example: 2012345678.tar

현재 제출하신 학생들 중, 프로젝트 설명 때 언급한 제출 규정을 지키지 않으신 분들이 몇 분 존재합니다.
과제 마감 기간이 끝남과 동시에 여러분의 과제는 제가 하나하나 수행시키는 것이 아닌, 쉘 스크립트를 이용하여 채점합니다.
따라서, 제출 규정을 지키지 않을 시 여러분의 과제 점수가 0점이 나올 수도 있다는 점을 명심해 주시기 바랍니다.

3) You cannot use optimization option (like -O series) in Makefile.
You can only change about used files.

Makefile에서 optimization option (-O series) 을 사용하시면 안됩니다.
Makefile 수정 권한을 드린 것은 여러분이 작성하고자 하는 코드 파일을 자유롭게 해드리기 위해서입니다.

4) You make only four output files (Initial_map.txt, Initial_pos.txt, Final_map.txt, Final_pos.txt) and print time in terminal.
If your code make or print any other things, then your point will be degraded.

프로젝트 실행이 끝났을 때, 4개의 아웃풋 파일 (Initial_map.txt, Initial_pos.txt, Final_map.txt, Final_pos.txt) 출력과 실행시간 출력만이 이루어져야 합니다.
그 이외의 요소가 발생할 시 점수에서 감점됨을 공지합니다.

5) You can use inline function option.
However, you cannot use that about stage function(devil, live_dead, plague, angel).
After Pthread project start, you cannot only apply run_game function and can use to devil, live_dead, ... functions at this time.

QnA에서 언급된 inline 옵션에 대해서 자유롭게 사용해도 된다고 언급을 했었습니다.
자유롭게 사용하시되, 해당 옵션은 각 stage(devil, live_dead, plague, angel) 함수에 적용하시는 것은 금지합니다.
Pthread 프로젝트에서는 run_game 함수에 적용하는 것만을 금지합니다. devil, live_dead, ...에도 이 때부터 적용 가능합니다.