Archive

Author Archive

Assignment 5 (CS427) – Game of Life

April 6, 2010 Leave a comment

ข้อกำหนดของโปรแกรม

  1. จำนวนโปรเซสทั้งหมดจะต้องมีจำนวนเท่ากับ (N/K)^2 + 1
  2. ค่าของความกว้างของบอร์ด(N) และขนาดของTile(K) จะต้องมีค่าอย่างน้อย 1 และ ค่าของ N จะต้องหารด้วย k ลงตัวเสมอ
  3. ค่าการสุ่มความน่าจะเป็นในการมีชีวิตของแต่ละเซลจะต้องมีค่าอยู่ระหว่าง [0, 100] เท่านั้น

การคอมไพล์โปรแกรมและการใช้งาน

  1. คอมไพล์โปรแกรมด้วยคำสั่ง mpicc -o Game_of_Life Game_of_Life.c จะได้ไฟล์โปรแกรมชื่อ Game_of_Life
  2. รันโปรแกรมด้วยคำสั่ง mpirun –np processnum Game_of_Life โดยจะต้องกำหนดจำนวนโปรเซสให้ถูกต้องตามข้อกำหนด
  3. โปรแกรมจะถามถึงค่าของ ความกว้างของบอร์ด(N) ขนาดของTile(K) จำนวนหน่วยเวลา(t) ต้องการอ่านค่าเริ่มต้นจากไฟล์หรือสุ่มจากโปรแกรม ถ้าเลือกอ่านค่าจากไฟล์จะต้องกำหนดชื่อไฟล์ด้วย หากเลือกสุ่มจากโปรแกรมจะต้องกำหนดค่าความน่าจะเป็นในการที่แต่ละช่องจะมีชีวิตด้วย และ ต้องการเซฟไฟล์ Immediate หรือไม่  ซึ่งจะต้องกรอกให้สอดคล้องกับจำนวนโปรเซสที่กำหนดไว้ หากข้อมูลที่กรอกไม่สอดคล้องหรือไม่ถูกต้องได้แก่
  • ค่า N หรือ k ไม่ใช่เลขจำนวนเต็มบวก
  • N หาร k ได้ไม่ลงตัว
  • จำนวนโปรเซสไม่ถูกต้อง
  • ไม่พบไฟล์ที่ต้องการอ่าน

เมื่อพบเงื่อนไขดังกล่าวโปรแกรมจะจบการทันงานโดนทันที ซึ่งจะต้องเริ่มทำการรันโปรแกรมใหม่

การออกแบบโปรแกรมและขั้นตอนการทำงาน

การทำงานของโปรแกรมจะใช้จำนวนโปรเซสเท่ากับจำนวนของ Tile ทั้งหมดบวกด้วย 1 เนื่องจากจะใช้โปรเซส 0 ในการติดต่อกับผู้ใช้ เขียนข้อมูลลงไฟล์ สุ่มค่าเริ่มต้น และใช้โปรเซสที่เหลือทั้งหมดในการคำนวนค่าของแต่ละ Tile ที่ได้รับมอบหมาย

1. โปรเซส 0 จะจองพื้นที่บอร์ดขนาด N x N เพื่อรับข้อมูลจากไฟล์หรือสุ่มขึ้น ส่วนโปรเซสอื่นทั้งหมดจะทำการจองบอร์ดย่อยขนาด (K + 2) x (K + 2) ซึ่งจะสร้างขอบเพิ่มให้กับแต่ละ Tile ในทุกด้านเพื่อใช้ในการคำนวน โดยบอร์ดย่อยที่สร้างขึ้นจะสร้างขึ้นเป็นจำนวน 2 บอร์ดเพื่อใช้ในการคำนวน จากนั้นส่งค่าของ N, k, t ไปยังทุกโปรเซสด้วยคำสั่ง MPI_Bcast()

2. จากนั้นโปรเซส 0 จะแบ่งบอร์ดเป็น Tile และส่งไปให้แต่ละโปรเซสเรียงตามลำดับจากซ้ายไปทางขวาและขึ้นแถวใหม่จนครบดังภาพที่ 1

ภาพที่ 1

3. โปรเซสอื่นทั้งหมดจะรับมาเก็บไว้ที่ตรงกลางของบอร์ดย่อยที่มีความยาวมากกว่าขนาดของ Tile อยู่ 2 ดังภาพที่ 2

ภาพที่ 2

4. ส่งข้อมูลระหว่างแต่ละโปรเซสเพื่อคำนวนเวลาถัดไปของแต่ละ Tile ด้วยการตรวจสอบว่าแต่ละโปรเซสจะต้องส่งค่าไปยังโปรเซสใดบ้าง และรับค่ามาจากโปรเซสที่ส่งค่าไปหาเสมอ

  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบนและไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้ายบน ดังลูกศรสีแดงในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)%c != 0 && (rank-1)/c > 0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวที่สองและหลักที่สองจำนวน 1 ค่าเท่านั้น ดังภาพที่ 4
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่างและไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวาล่าง ดังลูกศรสีเหลืองในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข rank%c != 0 && (rank-1)/c < c-1 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวรองสุดท้ายและหลักรองสุดท้ายจำนวน 1 ค่าเท่านั้น ดังภาพที่ 4
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบน ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านบน ดังลูกศรสีส้มในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c > 0 โดยจะส่งเฉพาะข้อมูลในแถวที่สอง ตั้งแต่หลักที่สองจนถึงหลักรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 5
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่าง ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านล่าง ดังลูกศรสีม่วงในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c < c-1 โดยจะส่งเฉพาะข้อมูลในแถวรองสุดท้าย ตั้งแต่หลักที่สองจนถึงหลักรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 5
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบนและไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวาบน ดังลูกศรสีเขียวในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c > 0 && rank%c !=0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวที่สองและหลักรองสุดท้ายจำนวน 1 ค่าเท่านั้น ดังภาพที่ 6
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่างและไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้ายล่าง ดังลูกศรสีน้ำเงินในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c < c-1 && (rank-1)%c != 0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวรองสุดท้ายและหลักที่สองจำนวน 1 ค่าเท่านั้น ดังภาพที่ 6
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวา ดังลูกศรสีฟ้าในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข rank%c !=0 โดยจะส่งเฉพาะข้อมูลในหลักรองสุดท้าย ตั้งแต่แถวที่สองจนถึงแถวรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 7
  • โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้าย ดังลูกศรสีดำในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)%c != 0 โดยจะส่งเฉพาะข้อมูลในหลักที่สอง ตั้งแต่แถวที่สองจนถึงแถวรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 7

หมายเหตุ: rank เป็นหมายเลขของโปรเซส, c เป็นจำนวนเต็มบวกที่ได้มาจาก N/k

ภาพที่ 3

ภาพที่ 4 ภาพที่ 5
ภาพที่ 6 ภาพที่ 7

MPI Defined Type ที่ใช้

MPI_Subboard_type : บอร์ดย่อยที่ได้จากการแบ่งเป็น Tile ของบอร์ดใหญ่เพื่อส่งจากโปรเซส 0 ไปยังโปรเซสอื่น
MPI_Type_vector(K, K, N, MPI_INT, &MPI_Subboard_type);

MPI_Subboard_type2 : บอร์ดย่อยที่ใช้ในการประมวลผลของแต่ละโปรเซส และรับส่งบอร์ดย่อยกับโปรเซส 0
MPI_Type_vector(K, K, K+2, MPI_INT, &MPI_Subboard_type2);

MPI_Boardrow_type : แถวของบอร์ดย่อยที่ใช้ในการส่งระหว่าง Tile ที่อยู่ด้านล่างและบน
MPI_Type_contiguous(K, MPI_INT, &MPI_Boardrow_type);

MPI_Boardcol_type : หลักของบอร์ดย่อยที่ใช้ในการส่งข้อมูลระหว่าง Tile ที่อยู่ด้านซ้ายและขวา
MPI_Type_vector(K, 1, K+2, MPI_INT, &MPI_Boardcol_type);

ตัวอย่างการใช้งานแบบอ่านค่าจากไฟล์

$ mpirun –np 5 Game_of_Life
Enter board size (N): 6
Enter tile size (K): 3
Enter time step (t): 2
Do you want to save immediate file (yes/no): yes
Read board from file (yes/no – if no board is initialize by random): yes
Enter input file name : inputboard2.txt

inputboard2.txt Board.Immediate Board.output
XX-XX-
—XXX
—-XX
X-X-X-
-X-X-X
XXX—
t = 0
XX-XX-
—XXX
—-XX
X-X-X-
-X-X-X
XXX—t = 1
–XX-X
–X—
——
-XX—
—XX-
XXX—t = 2
–XX–
–XX–
-XX—
–XX–
X–X–
-XXX–
–XX–
–XX–
-XX—
–XX–
X–X–
-XXX–

ตัวอย่างการใช้งานแบบสุ่มความน่าจะเป็นของการมีชีวิต

$ mpirun –np 5 Game_of_Life
Enter board size (N): 6
Enter tile size (K): 3
Enter time step (t): 8
Do you want to save immediate file (yes/no): no
Read board from file (yes/no – if no board is initialize by random): no
Random life cell probability (0-100): 60

RandomBoard.input Board.output
X-XX-X
-X–XX
-X—X
XX-XXX
–XXX-
XX-X-X
——
——
——
-XX—
X–X–
-XX—

ดาวน์โหลด : ซอร์สโค้ด, ตัวอย่าง input 1, ตัวอย่าง input 2

Advertisements

การ Live Migration ภายในเครื่อง

March 25, 2010 Leave a comment

การทำการ Live Migration ภายในเครื่องนั้นมีขั้นตอนดังนี้

1. เริ่มต้นด้วยการเปิดเครื่องปลายทางด้วยคำสั่ง kvm -m 512 host.img -incoming tcp:0.0.0.0:8000 โดย

  • -m 512 หมายถึงให้เปิดเครื่องโดยกำหนด memory ไว้ที่ 512 MB (ใส่หรือไม่ใส่ก็ได้)
  • host.img อิมเมจไฟล์ของเครื่องที่จะทำการย้าย
  • -incoming tcp:0.0.0.0:8000 เป็นการบอกว่าจะทำการ migrate ผ่านทาง tcp ที่ ip 0.0.0.0 และ port 8000

เมื่อเปิดเครื่องสำเร็จ ตัวเครื่องจะอยู่ในสถานะ stopped รอการย้ายการทำงานมาที่เครื่อง

2. เปิดเครื่องที่จะทำการ Migrate โดยใช้คำสั่ง kvm -m 512 host.img เหมือนทำการเปิด virtual machine ปรกติ

3. ทดสอบการทำงานของการ Migrate ด้วยการเปิดโปรแกรม Siag บนหน้าจอ Desktop

4. เข้าสู่ command mode ของ kvm ด้วยการกด ctrl+alt+2

5. พิมพ์คำสั่ง migrate -d tcp:0.0.0.0:8000 ลงไปเพื่อเป็นการบอกว่าให้ทำการ migrate ไปที่ ip 0.0.0.0 และ port 8000

6. จากนั้นที่เครื่องปลายทางจะสังเกตุเห็นว่าการทำงานของเครื่องต้นทางถูกย้ายมาทำงานที่เครื่องปลายทาง สังเกตุได้จากโปรแกรม Siag ที่ได้เปิดเอาไว้ก่อนทำการ migrate

Categories: Virtualization Tags: , ,

เว็บไซต์ทุนเรียนต่อ

March 13, 2010 Leave a comment
ช่วงนี้กำลังวางแผนว่าจะเรียนต่อหรือทำงานดี ก็เลยลองๆหาทุนดู
 
กลัวจะลืมเลยเอาเว็บไซต์มาแปะไว้ในนี้แล้วกัน
 
 
Categories: Uncategorized

การใช้งาน MPI บน Microsoft Visual Studio 2008

March 13, 2010 Leave a comment

วิธีนี้ใช้ได้กับโปรแกรม Microsoft Visual Studio 2008 เพื่อเอาไว้ทดสอบการเขียนโปรแกรม MPI บนวินโดวส์

1. ก่อนอื่นทำการดาวน์โหลด HPC Pack 2008 SDK จากลิงค์ http://www.microsoft.com/downloads/details.aspx?FamilyID=12887DA1-9410-4A59-B903-693116BFD30E&displaylang=en และติดตั้งโปรแกรม

2. เปิดโปรแกรม Microsoft Visual Studio 2008 สร้างโปรเจคใหม่ โดยเลือกที่ Visual C++ >> Win32 และเลือกรูปแบบโปรเจคเป็น Win32 Console Application ใส่ชื่อของโปรเจคที่ต้องการที่ช่อง Name ด้านล่าง



3. เมื่อเลือกที่ Win32 Console Application แล้วกด OK จะปรากฏหน้าต่างใหม่ขี้น ให้กดปุ่ม Next > และเลือกเช็ค Precompiled header ออก แล้วจึงกด Finish



4. หลังจากสร้างโปรเจคเสร็จแล้ว ให้คลิกขวาที่โปรเจคและเลือกที่ Properties  เลือกเมนูในส่วนของ Configuration Properties >> C/C++ >> General และเพิ่มพาธของที่อยู่เฮดเดอร์ไฟล์ โดยปกติแล้วจะอยู่ที่ C:\Program Files\Microsoft HPC Pack 2008 SDK\Include ในช่อง Additional Include Directories



5. เลือกเมนู Configuration Properties >> Linker >> General และใส่พาธของที่อยู่ไลบรารี ซึ่งปกติจะอยู่ที่ C:\Program Files\Microsoft HPC Pack 2008 SDK\Lib\i386 ในช่อง Additional Library Directories



6. เลือกเมนู Configuration Properties >> Linker >> Input  และพิมพ์ msmpi.lib ในช่อง Additional Dependencies



7. เลือกเมนู Configuration Properties >> Linker > System และในช่อง SubSystem ให้เลือกเป็น Console(/SUBSYSTEM:CONSOLE)



8. ทดสอบโปรแกรมโดยพิมพ์โค้ดดังต่อไปนี้

#include <stdio.h>
#include <mpi.h> 

int main(int argc, char* argv[])
{
	int rank, size;

	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	if(rank==0){
		printf("Hello Kitty form root\n");
	}
	else{
		printf("Hello Kitty from rank %d\n", rank);
	}

	MPI_Finalize();

	return 0;
}

9. Build โปรแกรมด้วย Build >> Build Solution แล้วรันโปรแกรมด้วยการออกคำสั่ง mpiexec -n 10 programname.exe (อยู่ในโฟลเดอร์ Debug หลังจาก build เสร็จ) จะได้ผลลัพท์ดังนี้

ข้อควรระวัง : ทุกครั้งที่ใช้ฟังก์ชัน printf() ต้องเพิ่มคำสั่ง fflush (stdout); ตามไปด้วยเสมอ (เป็นบัคที่มาจากการ Implement MPI ของ Microsoft)

แหล่งข้อมูลเพิ่มเติม

http://blogs.msdn.com/risman/archive/2009/01/04/ms-mpi-with-visual-studio-2008.aspx

http://www.cs.utah.edu/~delisi/vsmpi/

http://www.oerc.ox.ac.uk/resources/wcc/support/documentation/sub-documentation/mpi

Assignment 4 (CS427) – Use hpccluster and MPI programming

February 9, 2010 Leave a comment

ขั้นตอนการติดต่อเครื่อง hpccluster และคำสั่งพื้นฐาน

1. เมื่อเริ่มต้นติดต่อไปยังเครื่อง hpccluster.cs.tu.ac.th เป็นครั้งแรก ระบบจะถามถึง passphrase ที่ต้องการใช้ และตำแหน่งที่เก็บ passphrase เพื่อใช้ในการเข้ารหัส private key

2. ใช้คำสั่ง $ ssh-agent /bin/sh เพื่อให้สามารถสั่งงาน compute-node โดยที่ไม่จำเป็นจะต้องกรอก passphrase เข้าไปใหม่ และใช้คำสั่ง $ ssh-add เพื่อให้ private-key ถูกโหลดขึ้นไปยังหน่วยความจำ เมื่อเรียกโปรแกรมนี้ โปรแกรมจะถามถึง passphrase เพื่อใช้ในการถอดรหัส ให้กรอก passphrase ตามที่ได้ตั้งไว้

3. ใช้คำสั่ง $ cluster-fork uptime เพื่อแสดงว่าเครื่อง compute-node ใดบ้างที่ทำงานอยู่และมี workload เป็นอย่างไร ซึ่งเมื่อทำการ Redirect ออกมาเป็นไฟล์ด้วยคำสั่ง $ cluster-frok uptime > output และทำการโหลดไฟล์มายังเครื่องด้วยโปรแกรมจะได้ไฟล์ที่มีข้อมูลดังนี้

compute-0-14: down
compute-0-17:  21:04:52 up 30 days, 12:14,  0 users,  load average: 0.00, 0.00, 0.00

compute-0-20:  21:04:52 up 30 days, 12:15,  0 users,  load average: 0.00, 0.00, 0.00

compute-0-28: down
compute-0-29:  21:04:55 up 30 days, 12:14,  0 users,  load average: 0.00, 0.00, 0.00

compute-0-30:  21:04:55 up 30 days, 12:15,  0 users,  load average: 0.15, 0.08, 0.01

compute-0-31:  21:04:56 up 30 days, 12:15,  0 users,  load average: 0.00, 0.00, 0.00

compute-0-32: down

MPI Programming

1. คัดลอกโฟลเดอร์ของไฟล์โปรแกรม MPI ตัวอย่างโดยใช้คำสั่ง $ cp -r /opt/mpich/gnu/examples /home/cs4270904/examples ทำการคอมไพล์โปรแกรม cpi.c ด้วยคำสั่ง $ mpicc cpi.c –o cpi โดยจะได้ executable file ชื่อว่า cpi

2. ออกคำสั่ง $ lamboot เพื่อสร้าง LAM runtime system และออกคำสั่ง $ lamnodes เพื่อตรวจสอบว่ามีเครื่องใดอยู่ใน LAM runtime system ซึ่งควรจะมีเพียงเครื่องเดียว เนื่องจากยังไม่ได้กำหนดเครื่องอื่นเพิ่มเติม

3. รันโปรแกรม cpi ด้วยคำสั่ง $ mpirun –np 1 cpi โดยที่ –np1 หมายถึงให้รันโปรแกรมโดยใช้ 1 โพรเซส จะได้ผลลัพท์คือ

ทดสอบด้วยการเพิ่มจำนวนโพรเซสที่ใช้รันเป็น 4 และ 8 ตามลำดับ

โปรแกรม cpi ทำหน้าที่หาค่า Pi ซึ่งจากการทดสอบพบว่ายิ่งเพิ่มจำนวนโพรเซสก็จะใช้เวลาในการทำงานเพิ่มขึ้น เนื่องจากยังกำหนดให้ประมวลผลบนเครื่องเดียว และยิ่งเพิ่มจำนวนโพรเซสก็จะยิ่งได้ค่า Pi ที่แม่นยำขึ้น (Error ลดน้อยลง)

4. และเมื่อทดสอบการใช้งานแล้วให้ออกคำสั่ง $ lamhalt เพื่อปิด LAM runtime system

5. เพื่อที่จะรันโปรแกรมด้วยการใช้เครื่องหลายเครื่องช่วยกันประมวลผล จะต้องทำการสร้าง hostfile ที่จะระบุชื่อของเครื่องทั้งหมดที่จะใช้งาน (ดูเครื่องที่ปัจจุบันสามารถใช้งานได้จากคำสั่ง cluster-fork uptime) ซึ่งในที่นี้จะตั้งชื่อไฟล์ว่า machine จะเปิดระบบ LAM runtime system ใหม่โดยใช้คำสั่ง $ lamboot machines เพื่อให้เริ่มต้นการทำงานโดยมีเครื่องภายในไฟล์ machines เป็นเครื่อง cluster ที่จะร่วมกันทำงาน ไฟล์ machine ที่ใช้ เป็นดังนี้

hpccluster
compute-0-17
compute-0-20
compute-0-29
compute-0-30
compute-0-31

6. จากนั้นใช้คำสั่ง $ lamnodes เพื่อดูเครื่องทั้งหมดที่ทำงานอยู่

7. ทดสอบการรันโปรแกรม cpi อีกครั้ง ซึ่งแตกต่างจากเดิมในส่วนที่ครั้งนี้จะใช้เครื่องหลายเครื่องช่วยในการประมวลผลโดยออกคำสั่งคือ $ mpirun n1-5 –np 4 cpi ซึ่งหมายถึงให้ใช้เครื่อง n1 ถึง n5 ในการประมวลผล (ไม่ใช้เครื่อง hpscluster เป็น front node) และใช้โพรเซสจำนวนทั้งหมด 4 โพรเซส ได้ผลลัพท์คือ

และทดลองใช้ 8 โพรเซส

ผลลัพธ์ที่ได้คือทั้งการใช้ 4 และ 8 โพรเซสบนเครื่องที่มีจำนวนมากขึ้นจะทำให้สามารถประมวลผลได้เร็วขึ้น

8. คัดลอกโปรแกรม Master/slave จากเว็บ http://www.mcs.anl.gov/research/projects/mpi/tutorial/mpiexmpl/src2/io/C/main.html และเซฟไฟล์ด้วยชื่อ io.c จากนั้นทำการอัพโหลดขึ้นไปยังเครื่อง Server โดยโปรแกรมนี้มีการทำงานคือจะส่งข้อความจากโพรเซสที่เป็น Slave มายังโพรเซสที่เป็น Master และทำการแสดงผลออกทางหน้าจอ

9. คอมไพล์โปรแกรมด้วยคำสั่ง $ mpicc io.c –o io และทดสอบรันด้วยการใช้ 4 โพรเซส ซึ่งจะมีโพรเซสที่เป็น Master 1 โพรเซส และ Slave อีก 3 โพรเซส

Categories: Parallel Programming Tags: , ,

Assignment 3 (CS427) – Game of Life

February 3, 2010 Leave a comment

1. โปรแกรม Game of Life ที่เป็นการทำงานแบบ Sequential จำเป็นจะต้องมีอาร์เรย์จำนวน 2 ชุดในการเก็บข้อมูลของเวลาที่ต่างกันในการทำงาน และใช้ Pointer ในการสลับอาร์เรย์เพื่อประมวลผล

#include <stdio.h>
#include <time.h>
#define MAX_WIDTH 1000

FILE *f;
char board1[MAX_WIDTH * MAX_WIDTH];
char board2[MAX_WIDTH * MAX_WIDTH];
char *currentBoard;
char *pastBoard;
int maxx, maxy;

void init();                           	        /* initial board */
void rand_init_pop(int rand_size);      	/* initial population */
int in_bound(int i, int j);
int neighbor_num(int i, int j);
void process();
void print_board();
void write_to_file();

int main(){
     int i, t = 10;
     int randnum = 0;

     printf("Enter board width : ");
     scanf("%d", &maxx);
     printf("Enter board height : ");
     scanf("%d", &maxy);
     printf("Enter number of random population : ");
     scanf("%d", &randnum);
     printf("Enter time step : ");
     scanf("%d", &t);

     pastBoard = board1;
     currentBoard = board2;

     init();
     rand_init_pop(randnum);

     f = fopen("sequential_board.txt", "w");

     for(i=0;i<t;i++){
          fprintf(f, "t = %d\n", i);
          write_to_file();
          process();
     }
     fprintf(f, "t = %d\n", i);
     write_to_file();

     fclose(f);

     return 0;
}
void init(){
     int i, j;
     for(i=0;i<maxy;i++) for(j=0;j<maxx;j++)
          board1[i * maxx + j] = board2[i * maxx + j] = 'O';
}
void rand_init_pop(int rand_size){
     int i, x, y;
     srand( time(0));

     for(i=0;i<rand_size;i++){
          y = rand() % maxy;
          x = rand() % maxx;
          if(pastBoard[y * maxx + x] == 'X') i--;
          else pastBoard[y * maxx + x] = 'X';
     }
}
int in_bound(int i, int j){
     if(i<0 || j=maxy || j>=maxy)    return 0;
     else                                    return 1;
}
int neighbor_num(int i, int j){
     int num = 0;
     if( in_bound(i-1,j-1) && pastBoard[(i-1) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i-1, j ) && pastBoard[(i-1) * maxx + ( j )]=='X' ) num++;
     if( in_bound( i ,j-1) && pastBoard[( i ) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i+1,j+1) && pastBoard[(i+1) * maxx + (j+1)]=='X' ) num++;
     if( in_bound(i+1, j ) && pastBoard[(i+1) * maxx + ( j )]=='X' ) num++;
     if( in_bound( i ,j+1) && pastBoard[( i ) * maxx + (j+1)]=='X' ) num++;
     if( in_bound(i+1,j-1) && pastBoard[(i+1) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i-1,j+1) && pastBoard[(i-1) * maxx + (j+1)]=='X' ) num++;
     return num;
}
void process(){
     int i,j;
     char* tmp;

     for(i=0;i<maxy;i++){
          for(j=0;j<maxx;j++){
               //For a space that is 'populated'
               if(pastBoard[i * maxx + j]=='X'){
                    //Each cell with one or no neighbors dies, as if by loneliness.
                    if(neighbor_num(i,j) <= 1) currentBoard[i * maxx + j] = 'O';
                    //Each cell with two or three neighbors survives.
                    else if(neighbor_num(i,j) <= 3) currentBoard[i * maxx + j] = 'X';
                    // Each cell with four or more neighbors dies, as if by overpopulation.
                    else currentBoard[i * maxx + j] = 'O';
               }
               //For a space that is 'empty' or 'unpopulated'
               else{
                    // Each cell with three neighbors becomes populated.
                    if(neighbor_num(i,j) == 3) currentBoard[i * maxx + j] = 'X';
                    else currentBoard[i * maxx + j] = 'O';
               }
          }
     }
     tmp = pastBoard;
     pastBoard = currentBoard;
     currentBoard = tmp;
}
void write_to_file(){
     int i, j;
     for(i=0;i<maxy;i++){
          for(j=0;j<maxx;j++){
               if(pastBoard[i * maxx + j]=='X')    fprintf(f, "1”);
               else                                fprintf(f, "0”);
          }
          fprintf(f, "\n");
     }
     fprintf(f, "\n");
}

เมื่อเริ่มต้นโปรแกรม โปรแกรมจะให้ใส่ข้อมูลขนาดความกว้าง และความสูงของตารางที่จะใช้ จากนั้นจะถามถึงจำนวน Cell ที่มีชีวิตเริ่มต้นที่ต้องการกำหนด โดยจะมีตำแหน่งแบบสุ่ม และสุดท้ายจะถามถึง จำนวนหน่วยเวลาที่ต้องการทำการ Simulation เมื่อใส่ข้อมูลครบแล้วโปรแกรมจะทำงาน และเขียนข้อมูลของตารางในแต่ละช่วงเวลาไปยังไฟล์ที่ชื่อ “sequential_board.txt”


2. การทำงานของโปรแกรม Game of Life บนจีพียู ใน 1 time step จะต้องเข้าถึงหน่วยความจำเฉลี่ยประมาณ 8 ครั้งต่อ 1 เทรด ดังนั้นเพื่อให้มีความรวดเร็วในการทำงาน จะต้องทำการคัดลอดข้อมูลจาก Global Memory มายัง Shared Memory ก่อน เพื่อให้เข้าถึงหน่วยความจำได้เร็วขึ้น โดยวิธีที่ใช้คือการแบ่งการทำงานออกเป็นเทรดบล็อคโดยที่ในตอนเริ่มต้นการทำงาน แต่ละเทรดบล็อคจะต้องคัดลอกข้อมูลในส่วนของ cell ที่มีพื้นที่ติดกันกับพื้นที่ที่เทรดบล็อคนั้นรับผิดชอบมาด้วย แต่ในการเขียนข้อมูลจะเขียนข้อมูลลงใน Global Memory ในช่องที่เทรดบล็อคนั้นรับผิดชอบเท่านั้น

#include <stdio.h>
#include <math.h>
#include <time.h>
#define MAX_WIDTH 500
#define TILE_WIDTH 16
#define TY threadIdx.y
#define TX threadIdx.x

void rand_init_pop(int *board, int maxx, int maxy, int rand_size);
void write_to_file(FILE *f, int *board, int maxx, int maxy);

__global__ void process(int *board, int maxx, int maxy);

int main(){
     int *board, *d_board, i, t;
     int maxx, maxy, size, randnum;
     FILE *f;

     printf("Enter board width : ");
     scanf("%d", &maxx);
     printf("Enter board height : ");
     scanf("%d", &maxy);
     printf("Enter number of random population : ");
     scanf("%d", &randnum);
     printf("Enter time step : ");
     scanf("%d", &t);
     size = sizeof(int) * maxx * maxy;

     f = fopen("cuda_board.txt", "w");

     board = (int*)malloc(size);
     cudaMalloc((void**)&d_board, size);
     rand_init_pop(board, maxx, maxy, randnum);

     dim3 blockDim(TILE_WIDTH+2, TILE_WIDTH+2);
     dim3 gridDim(ceil(maxy*1.0/TILE_WIDTH), ceil(maxx*1.0/TILE_WIDTH));

     cudaMemcpy(d_board, board, size, cudaMemcpyHostToDevice);

     for(i=0;i<t;i++){
          fprintf(f, "t = %d\n", i);
          write_to_file(f, board, maxx, maxy);

          process<<>>(d_board, maxx, maxy);
          cudaMemcpy(board, d_board, size, cudaMemcpyDeviceToHost);
     }
     fprintf(f, "t = %d\n", i);
     write_to_file(f, board, maxx, maxy);

     fclose(f);
     free(board);
     cudaFree(d_board);

     return 0;
}

void init(int *board, int maxx, int maxy){
     int i, j;
     for(i=0;i<maxy;i++) for(j=0;j<maxx;j++)
          board[i * maxx + j] = 0;
}
void rand_init_pop(int *board, int maxx, int maxy, int rand_size){
     int i, x, y;
     srand( time(0));
     init(board, maxx, maxy);

     for(i=0;i<rand_size;i++){
          y = rand() % maxy;
          x = rand() % maxx;
          if(board[y * maxx + x] == 1) i--;
          else board[y * maxx + x] = 1;
     }
}
void write_to_file(FILE *f, int *board, int maxx, int maxy){
     for(int i=0;i<maxy;i++){
          for(int j=0;j<maxx;j++)
               fprintf(f, "%d", board[i * maxx + j]);
          fprintf(f, "\n");
     }
     fprintf(f, "\n");
}

__global__ void process(int *board, int maxx, int maxy){
     __shared__ int sboard[TILE_WIDTH+2][TILE_WIDTH+2];

     int i = (blockIdx.x * TILE_WIDTH) + TX - 1;
     int j = (blockIdx.y * TILE_WIDTH) + TY - 1;

     if(i<=maxy && j=0 && j>=0 && i<maxy && j0 && TX0 && TY<TILE_WIDTH){
          int n = 0;
          n += sboard[TY+1][TX+1];
          n += sboard[TY+1][TX-1];
          n += sboard[TY-1][TX-1];
          n += sboard[TY-1][TX+1];
          n += sboard[TY+1][ TX ];
          n += sboard[ TY ][TX+1];
          n += sboard[ TY ][TX-1];
          n += sboard[TY-1][ TX ];

          if(sboard[TY][TX]==1 && n!=2 && n!=3)
               board[boardidx] = 0;
          else if(sboard[TY][TX]==0 && n==3)
               board[boardidx] = 1;
          }
     }
}

เมื่อรันโปรแกรม โปรแกรมจะถามข้อมูลเช่นเดียวกับโปรแกรม Sequential แต่ข้อมูลจะเขียนลงไปที่ไฟล์ที่มีชื่อว่า “cuda_board.txt”

สามารถดาวน์โหลดไฟล์โปรแกรมได้ที่ด้านล่าง
GameOfLife.c
GameOfLifeCUDA.cu

Assignment 2 (CS427)

January 10, 2010 Leave a comment

1. การทำให้โปรแกรมมีลักษณะการทำงานแบบ Parallelism มากที่สุด จะต้องทำการวิเคราะห์ความสัมพันธ์ของโปรแกรม ในส่วนต่างๆว่ามีส่วนใดที่สามารถทำงานพร้อมกันได้โดยดูจากกราฟ

จากโปรแกรมตัวอย่างเมื่อเขียนความสัมพันธ์ในรูปแบบกราฟจะได้กราฟลักษณะข้างต้น ซึ่งหมายความว่าลูปที่ 2 และ 3 ที่เป็นส่วนที่คำนวนค่าของ c และ d สามารถทำงานพร้อมกันได้ ดังนั้นจึงสามารถใช้คำสั่ง #pragma omp sections ในส่วนนี้ และภายในลูปแต่ละลูปก็มีไม่ความสัมพันธ์กันระหว่างแต่ละการวนรอบสังเกตุได้จากการอ้างอิงถึง index เดียวกันในแต่ละการวนรอบเท่านั้น ดังนั้นทุกลูปสามารถใช้คำสั่ง #pragma omp for เพื่อให้เกิดการทำงานแบบขนานขึ้นในแต่ละลูป

โดยสามารถเขียนเป็นโปรแกรมได้ดังดังนี้

#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#define N 50

int main (int argc, char *argv[])
{
     int i, nthreads, tid;
     float a[N], b[N], c[N], d[N];
     float pa[N], pb[N], pc[N], pd[N];

     /* Sequential Program */
     for (i=0; i<N; i++) {
          a[i] = i * 1.5;
          b[i] = i + 22.35;
          c[i] = d[i] = 0.0;
     }

     for (i=0; i<N; i++){
          c[i] = a[i] + b[i];
     }
     for (i=0; i<N; i++){
          d[i] = a[i] * b[i];
     }

     /* Parallel Program with OpenMP */
     #pragma omp parallel for
     for (i=0; i<N; i++) {
          pa[i] = i * 1.5;
          pb[i] = i + 22.35;
          pc[i] = pd[i] = 0.0;
     }

     #pragma omp parallel sections
     {
          #pragma omp section
          #pragma omp parallel for
          for (i=0; i<N; i++){
               pc[i] = pa[i] + pb[i];
          }

          #pragma omp section
          #pragma omp parallel for
          for (i=0; i<N; i++){
               pd[i] = pa[i] * pb[i];
          }
     }

     /* check answers */
     for(i=0;i<N;i++){
          if(c[i]!=pc[i] || d[i]!=pd[i]){
               printf("Compute Error\n");
               break;
          }
     }
     if(i==N) printf("Corrected Answer\n");

     return 0;
}

โปรแกรมดังกล่าวจะทำงานทั้งหมดสองครั้งคือ คำนวนเชิงลำดับ (Sequential) และคำนวนแบบขนาน (Parallel) ด้วยการใช้ OpenMP หลังจากนั้นจะนำคำตอบมาตรวจสอบว่าการคำนวนแบบขนานให้ผลลัพท์เช่นเดียวกับการทำงานเชิงลำดับหรือไม่ ซึ่งหากคำนวนได้ถูกต้องจะปรากฎผลลัพท์ขึ้นมาเป็น Corrected Answer และจะปรากฎผลลัพท์ว่า Compute Error หากทำงานผิดพลาด ในที่นี้จะทำการคอมไพล์ด้วยโปรแกรม gcc เวอร์ชัน 4 ด้วยคำสั่ง

$gcc-4 –fopenmp program1.c –o program1

และเมื่อนำโปรแกรมไปรันทดสอบ ผลลัพท์ที่ได้คือ Corrected Answer หรือโปรแกรมทำงานได้ถูกต้อง ถึงแม้โปรแกรมนี้จะมีความเป็น Parallelism สูง แต่ในการทำงานจริงจะทำงานได้ช้า เนื่องจากโปรแกรมจะเสียเวลาในการสร้างเทรดขึ้นมาจำนวนมาก ซึ่งไม่คุ้มกับการคำนวนข้อมูลที่มีจำนวนน้อย ในการทำงานจริงเพื่อให้มีประสิทธิภาพสูงสุดอาจจะกำหนดให้มีการทำงานแบบขนานเพียงบางส่วนเท่านั้น เพื่อลด overhead ในการสร้างเทรด


2. ในข้อนี้จะทำการเปลี่ยนโปรแกรมเชิงลำดับให้เป็นโปรแกรมแบบขนานที่ทำงานได้บนจีพียู ซึ่งจะเขียนโปรแกรมที่คำนวนบนซีพียูและจีพียูจากนั้นจะนำคำตอบที่ได้มาตรวจสอบว่าได้ค่าที่เหมือนกัน ซึ่งการคำนวนค่าของ Floating-point บนซีพียูและจีพียูนั้นให้ค่าที่แตกต่างกันเล็กน้อย ดังนั้นเทียบค่าของ Floating-point ที่คำนวนได้ด้วยฟังก์ชัน floatIsEqual ในโปรแกรม

#include <stdio.h>
#include <time.h>
#define DELTA 0.001

int floatIsEqual(float a, float b){
     if( (b<a+DELTA) && (b>a-DELTA) ) return 1;
     else  return 0;
}

__global__ void GPUfunction(float *A, float *B, float *C){
     int i = blockIdx.x * blockDim.x + threadIdx.x;

     if(i<1024)       C[i] = A[i] + B[i];
     else if(i<2048) C[i] = A[i] * B[i];
     else if(i<3072) C[i] = A[i] - B[i];
     else if(i<4096) C[i] = A[i] / B[i];
}

void CPUfunction(float *A, float *B, float *C){
     int i;

     for(i=0; i<1024; i++)              C[i] = A[i] + B[i];
     for(i=1024; i<2048; i++)         C[i] = A[i] * B[i];
     for(i=2048; i<3072; i++)         C[i] = A[i] - B[i];
     for(i=3072; i<4096; i++)         C[i] = A[i] / B[i];
}

int main(){
     int i;
     float A[4096], B[4096], C[4096];
     float *hA, *hB, *hC;
     float *dA, *dB, *dC;
     int size = 4096 * sizeof(float);

     hA = (float*)malloc(size);
     hB = (float*)malloc(size);
     hC = (float*)malloc(size);

     cudaMalloc((void**)&dA, size);
     cudaMalloc((void**)&dB, size);
     cudaMalloc((void**)&dC, size);

     /* initialize */
     srand(time(0));
     for(i=0;i<4096;i++){
          A[i] = hA[i] = rand() % 40;
          // make sure that B is not zero
          B[i] = hB[i] = rand() % 39 + 1;
     }

     /* GPU code */
     cudaMemcpy(dA, hA, size, cudaMemcpyHostToDevice);
     cudaMemcpy(dB, hB, size, cudaMemcpyHostToDevice);
     GPUfunction<<<8, 512>>>(dA, dB, dC);
     cudaMemcpy(hC, dC, size, cudaMemcpyDeviceToHost);

     /* CPU code */
     CPUfunction(A, B, C);

     /* check answers from CPU and GPU are same */
     for(i=0;i<4096;i++){
          if(!floatIsEqual(C[i], hC[i])){
               printf("Compute Error\n");
               break;
          }
     }
     if(i==4096) printf("Corrected Answer\n");

     free(hA);
     free(hB);
     free(hC);

     cudaFree(dA);
     cudaFree(dB);
     cudaFree(dC);

     return 0;
}

ทำการคอมไพล์โปรแกรมด้วยคำสั่ง

$nvcc  program2.cu –o program2

ได้ผลลัพท์ออกมาเป็น Corrected Answer ซึ่งหมายถึงโปรแกรมทำงานได้ถูกต้อง การคำนวนแบบขนานจากจีพียูให้ผลลัพท์ตรงตามการคำนวนจากซีพียู


3. โปรแกรมนี้สามารถเพิ่มประสิทธิภาพได้ด้วยการใช้ Shared Memory และ Parallel Reduction ในการรวมข้อมูลหลังจากนั้นจึงทำการคำนวน โค้ดของโปรแกรมเหมือนกับข้อ 2 ยกเว้นในส่วนของฟังก์ชัน GPUfunction และ CPUfunction ซึ่งทำการเปลี่ยนแปลงดังนี้

GPUfunction :

__global__ void GPUfunction(float *A, float *B, float *C){
     int i = blockIdx.x * blockDim.x + threadIdx.x;
     __shared__ float ssuma[512];
     float sum;
     int s, tid = threadIdx.x;

     /* copy global mem to shared mem synchonously */
     ssuma[tid] = A[i];
     __syncthreads();

     /* parallel reduction */
     for(s=256; s>0; s/=2){
          if(tid<s)  ssuma[tid] = ssuma[tid] + ssuma[tid+s];
          __syncthreads();
     }
     sum = ssuma[0];

     if(i<1024)        C[i] = sum + B[i];
     else if(i<2048) C[i] = sum * B[i];
     else if(i<3072) C[i] = sum - B[i];
     else if(i<4096) C[i] = sum / B[i];
}

CPUfunction :

void CPUfunction(float *A, float *B, float *C){
     int i;
     float SUMA[8];

     /* initialize SUMA */
     for(i=0;i<8;i++)           SUMA[i] = 0.0;
     for(i=0;i<4096;i++)     SUMA[i/512] += A[i];

     for(i=0; i<1024; i++)
          C[i] = SUMA[i/512] + B[i];
     for(i=1024; i<2048; i++)
          C[i] = SUMA[i/512] * B[i];
     for(i=2048; i<3072; i++)
          C[i] = SUMA[i/512] - B[i];
     for(i=3072; i<4096; i++)
          C[i] = SUMA[i/512] / B[i];

}

ทำการคอมไพล์โปรแกรมด้วย nvcc โดยใช้คำสั่ง

$nvcc  program3.cu –o program3

ซึ่งเมื่อรันโปรแกรมแล้วให้ผลลัพท์ถูกต้อง และแสดงข้อความว่า Corrected Answer เช่นเดียวกันในข้อ 2

ดาวน์โหลดโปรแกรมทั้ง 3 โปรแกรมได้ที่ด้านล่าง
program 1
program 2
program 3