# NTHU-courses The Projects and Homeworks in National Tsing Hua University (NTHU)

====================================================

Parallel Programming: (Graduate Program)

Testing System: On Quanta cluster 11 nodes, each one has 12 processes, 96GB memory with 4TB storage space. Each project must measure and analyze the performance and scalability of implemented programs.

Proj_1. Basic odd-even sort and advanced odd-even sort : implementing basic and advanced odd-even sort with MPI and parallelizing I/O actions with collective MPI-I/O.

Proj_2. Single Roller Coaster Car Problem And N-body Problem

Single Roller Coaster Car Problem  :
           2.1 Simulate Single Roller Coaster Car action and 
                prevent synchronization by using conditional variable or mutex lock.
           
N-body Problem  :        
           2.2 Parallel N-body's sequential code by using Pthread and OpenMP.
           2.3 Implement Barnes-Hut Algorithm by Pthread: Must parallelizing
                building tree phase and simulation phase 

Proj_3. Manderlbrot Set Problem: Implementing both the "static" and "dynamic" scheduling versions to evaluate its loading balance status.

3.1. Distributed memory in MPI
3.2. Shared memory in OpenMP
3.3. Hybrid (distributed-shared) memory ( MPI + OpenMP)

Proj_4. Blocked All-Pairs Shortest Paths Algorithm in CUDA:

4.1. Single GPU: 
                  implement Blocked All-Pairs Shortest Paths Algorithm in CUDA.
4.2. Multi-GPU in MPI version: 
                  implement programs using multiple GPUs on multi nodes by MPI.
43.3 Multi-GPU in OpenMP version:
                  implement programs using multiple GPUs on multi nodes by OpenMP.

====================================================

Advance Programming Techniques and Implementation: Solve ACM & UVA problem.

01_Binary Search:　Uva_10341_Solve_It, Uva_714_Copying_book

02_Sorting: Uva_812_Trade_On_Verweggistan, Uva_10125_Sumsets

03_Big_Number: Uva_623_500!, Uva_10023_Square_Root

04_Prime_Number: Uva_294_Divisors, Uva_10140_Prime_Distance

05_Simulation: Uva_246_10-20-30. Uva_305_Joseph

06_Graph_DFS:　 Uva_10608_Friends, Uva_315_Network

07_EulerPath: Uva_302_John's_Trip, Uva_10248_The_Integer_All-Time_Champ　

08_SingleSource_ShortestPath: Uva_318_Domino_Effect, Uva_10537_Toll!_Revisited

09_BFS: Uva_816_Abbott_Revenge, Uva_10603_Fill

10_All-pairs_Shortest_Path:　 Uva_247_Calling_Circles, Uva_10269_Advaneture_Of_Super_Mario

11_Branch_And_Bound_1: Uva_10318_Security_Panel, Uva_818_Cutting_Chains

12_Branch_And_Bound_2: Uva_10422_Knights_In_FEN, Uva_704_Colour_Hash

====================================================

Computer Architecture:

Proj_1. MIPS Single Cycle CPU Simulator: Implement a single-cycle, functional processor simulator according to the reduced MIPS R3000 ISA.

Proj_2. MIPS Pipelined CPU Simulator: Implement a pipelined, functional processor simulator with forwarding unit and data-hazard dectection.

Proj_3. MIPS Cache Memory Pagetable CPU Simulator: a simulator with memory hierarchy, Translation-Lookaside Buffer (TLB), virtual page table and cache mechanism with write back and write through policy.

Proj_Tools: Assembler and disassembler for CPU Simulator.

====================================================

Operation System:

HW_1. User-Mode and Kernel-Mode Processor Monitor: a monitor oversees it own child’ process status and delivers information between different processers.

HW_2. River and Frog Arcade Game: multi-thread programming with XLib

HW_3. Virtual Memory Management in CUDA: implementing GPU virtual-memory system with LRU replacement policy.

HW_4. File System Management in CUDA: Implement a simple file system in a kernel function of GPU that have single thread, limit global memory as volume.

HW_5. I/O System DMA (Kernel-mode) Device Simulator: keyboard device simulator in Kernel-Mode with blocking and non-blocking I/O operation.

====================================================