path: root/spec/notes.txt

*** Research Notes for the Project ***


+---------------------------------------------------------------+
| NOTE: INCLUDES ONLY THE ABSOLUTE BASICS OF A GPU ARCHITECTURE |
+---------------------------------------------------------------+


* GPU Parts:
	1. Compute Cores
	2. Memory Controllers/Partitions
	3. Driver

* High-Level Architecture:
	1. Computing Cores
		+ threads grouped into warps (e.g. 32 threads)
		+ warps executed separately
		+ when branch divergence for warps' threads -> [Thread Reconvergence]
		+ for selecting which warp to execute -> [Warp Scheduling]
		+ each warp can execute multiple instructions before switching -> [Instruction Flow]
	2. Memory Controllers
		+ 


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


+-----------------------+
|       SIMT Core       |
+-----------------------+


* Thread Reconvergence
	Two Options:
	1) [SIMT] Stack-based: (easier to implement ; potential deadlocks)
		+ Runs through all the instructions serially
		+ Has an "Active Mask" -> which threads in the warp should execute the instruction
		+ Implemented via a stack that stores | Return PC | Next PC | Active Mask | columns
		+ Top of the stack -> the active mask to be used
		+ When branch divergence -> change next PC of current TOS ; add two new rows for the new branches
		+ TOS should be the branch with the most active threads when diverging
		+ Note: seems like might need to do some post-compilation inference work ??
		  (for determining return / reconv. PCs, idk yet, or maybe do it during runtime)
		+ For warp-splits, implement Multi-Path Stack, so no idleing left
		+ Example:
			```
			Assuming the following kernel:

			A;
			if (id % 2 == 0) {
				B;
				if (id == 0) {
					C;
				} else {
					D;
				}
				E;
			} else {
				F;
			}
			G;

			Assume 4 threads in a warp (ids from 0 to 3)

			Initially the stack looks like this:
			reconv. PC | next PC | Active Mask
			null       | A       | 1 1 1 1      <- TOS

			When 1st branch divergence occurs:
			reconv. PC | next PC | Active Mask
			null       | G       | 1 1 1 1      <- change A to G since that's where threads will reconv.
			G          | F       | 0 1 0 1
			G          | B       | 1 0 1 0      <- TOS

			When B finishes executing, another divergence
			reconv. PC | next PC | Active Mask
			null       | G       | 1 1 1 1
			G          | F       | 0 1 0 1
			G          | E       | 1 0 1 0      <- change to E
			E          | D       | 0 0 1 0
			E          | C       | 1 0 0 0      <- TOS

			After C finishes and PC goes to E -> pop the stack
			reconv. PC | next PC | Active Mask
			null       | G       | 1 1 1 1
			G          | F       | 0 1 0 1
			G          | E       | 1 0 1 0 
			E          | D       | 0 0 1 0      <- TOS

			D finishes; pop the stack (PC D gets to E)
			reconv. PC | next PC | Active Mask
			null       | G       | 1 1 1 1
			G          | F       | 0 1 0 1
			G          | E       | 1 0 1 0      <- TOS

			...

			so on, reaching to PC G

			```
	2) [SIMT] Stack-less: (harder to implement ; better performance ; no deadlocks w/ yielding)
		+ Add a barrier participation mask
		+ Thread active bits -> track whether the thread is being executed or not
		  => getting group of threads that the scheduler that can decide between to execute
		  (group threads by same PC)
		+ Thread States -> ready to execute or blocked (no yielding yet for deadlock)
		+ When reaching "add_barrier [barrier]" instruction
		  creates new barrier mask, includes all the active threads inside the mask
		+ When reaching "wait [barrier]" ->
		  -> execute NOP until all threads in the barrier got to this point as well
			 (track using a barrier state field)
		+ Example:
			```
			Assume the following kernel:

			A;
			add_barrier b0;
			if (id % 2 == 0) {
				B;
			} else {
				C;
				add_barrier b1;
				if (id == 1) {
					D;
				} else {
					E;
				}
				wait b1;
				F;
			}
			wait b0;
			G;

			Imagine 8 threads per warp
			During A:
			All trheads are active:

			0 1 2 3 4 5 6 7
			---------------
			1 1 1 1 1 1 1 1 <- active threads

			Adding barrier b0:
			Creating new barrier participation mask:

			0 1 2 3 4 5 6 7
			---------------
			1 1 1 1 1 1 1 1 <- b1 barrier mask
			0 0 0 0 0 0 0 0 <- b1 barrier state [initial]


			Half of threads go to B and other half to C => two thread groups

			0 1 2 3 4 5 6 7
			---------------
			1 0 1 0 1 0 1 0 <- warp split (two groups)

			Execute one thread group at a time

			Adding new barrier b2:
			Active threads are the half executing C with odd thread ids

			0 1 2 3 4 5 6 7
			---------------
			0 1 0 1 0 1 0 1 <- b2 barrier mask
			0 0 0 0 0 0 0 0 <- b2 barrier state [initial]

			One thread jumps to D and other odd id-ed threads jump to E
			=> now there are three thread groups to schedule and execute

			Reaching `wait b1`
			Threads who reach this -> get state blocked (not executable) =>
			=> thus, when executing thread group, blocked ones should get "ignored"

			When b2 barrer sate == b2 barrier mask, 
			Make all threads executable again => two thread groups remaining 
			(since two different PCs that threads are at to execute)

			Similar when waiting for b1 barrier
			```


* Warp Scheduling
	+ Round-Robin (RR) scheduling
		> same # of instructions executed per warp => all warps get equal attention
	+ Greedy-then-Oldest (GTO) scheduling
		> when a warp stalls -> offload it and load in the oldest warp
	+ Choose whichever one for now, upgrade later if needed
	------
	  Ex: execute warp instructions until an async mem req was issued (w/ cache miss)


* Instruction Flow
	+ Each warp having access to an "Instruction Buffer" (I-Buf)
	+ Each warp has a "Scoreboard" assigned to it
	  with 3 or 4 entries, each entry an id of a register
	  Ex: containing 3 entries R1, R5, R8
	+ Instruction get fetched from the Instruction Cache (I-Cache)
	+ If any of the source or destination registers of the instruction
	  matches with the scoreboard entries, then hold the instr. inside the buf
	  but do not yet execute
	+ When the current instruction finishes executing, it will clear some of the
	  registers in the scoreboard, resulting in some instruction from the buffer
	  to be eligible to be executed
	+ When I-Buf is full, stall / drop the fetched instruction
	+ Note: to avoid structural hazards, implement instruction replay


* Operand Collector
	+ When an instruction is issued, it gets decoded, and its operands get collected
	+ Ex: add r1 r2 r3 ->
	      -> 2 regs r2 and r3 to be read, added, and then stored inside r1
	+ When the warp issues the instruction, it goes to a "collector unit"
	+ For the example, assume warp w0 issues the add instruction => we get a collector unit
	  [Note: operand data field - 32 (warp size) x 4 bytes (reg size: 32-bit) = 128 bytes]
	  +----------------------------------------+
	  |                   w0                   |
	  +-----------+-----+-------+--------------+
	  | valid bit | reg | ready | operand data |
	  +-----------+-----+-------+--------------+
	  |     1     | r2  | 1     | 1, 9, ..., 4 |
	  |     1     | r2  | 0     | 3, -, ..., - |
	  |     0     | -   | -     | -            |
	  +-----------+-----+-------+--------------+
	+ When all operands are ready, the instruction is issued to the SIMD exec unit
	+ To avoid WAR hazards, just allow unique warps for collector units
	  (or add a separate bloomboard filter for less slowdown but more complex)


* Warp Compaction
	+ Idea: warps execute "in a same manner"
	  Ex: assume 10 warps executing and reaching a branch at the same time
	   => each warp will have 16 threads going to branch B1 and other half to B2
	   => can rearrange the static threads into different warps s.t.
	      5 warps' threads execute B1 and other 5 warps execute B2
	   [Called Dynamic Warp Formation]
	   Issue: non-coalesced memory accesses + can starve some threads!
	+ Other methods mostly focus on thread-block level compaction
	  => sync-ing warps between each other instead of threads within them
	+ Look into software compaction (later though)
	+ Warp Scalarization? If multiple threads operate on same data, their output is the same => 
	  just run on one thread


* Register File
	+ Thousands of in-flight registers, can consume ~10% of total power
	+ Implement a register file cache (RFC)
	+ RFC allocates a new entry (FIFO replacements) for the dest operand of instructions
	+ After an entry is kicked out, write the value back to the reg file
	+ Mark registers in the RFC that are only read (dead bit) => no need to write back to reg file
	+ Categorize warps into 'active' and 'non-active' warps;
	  allow access to RFC only to 'active' warps
	  if warp becomes 'inactive', remove its entries from RFC
	+ More efficient to do with the compiler (operand register file),
	  s.t. compiler decides which values to move to OFC
	+ Other ways to reduce reg file area / usage are targeted more torwards ASICs than FPGAs


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


+-----------------------+
|     Memory System     |
+-----------------------+


* Scratchpad/Shared Memory & L1 Data Cache
	+ "scratchpad memory" refers to the memory accessible to all threads in the CTA
	+ NOTE: due to each SIMT Core having their own L1 cache,
	  L1 cache should only store "local memory" data and global read-only mem data
	+ Memory access request:
		1. Mem access req is sent from the load/store unit to the L1 cache
		   Mem access reqs consist of mem addrs (one for each thread in the warp) + operation type (ld/st)
		2. If the reqs cause bank conflicts -> split the reqs into two groups: [Arbiter]
		   threads' reqs that do NOT cause bank conflicts and those that cause
		   only execute the ones that do not cause conflicts and replay the instructions of the other group
		3. Memory is direct mapped => tag unit then determines the bank each thread will be using
		4. The data is looked up in the bank and then returned to the thread's lane using data crossbar
		5. If a cache miss is registered, the req goes to Pending Request Table (PRT)
		6. Reqs from PRT go to the MMU, which translated the virt. addr to physical one
		   then sends to L2 cache -> DRAM
		   the response is sent back to Fill Unit that fills the L1 cache with the results
		   and passes the info to the arbiter, which then re-reqs the loaded value (guaranteed hit this time)
		7. All data write reqs go to a "Write Buffer", which forwards the requests via
		   data crossbar to local reg file or to the MMU for global memory writes


* L1 Texture Cache
	+ For now, make the memory unified with L1 Data Cache (since only read-only values are cached)


* On-Chip Interconnection Network
	+ For high mem bandwidth, GPUs are connected to multiple DRAMs
	+ Mem traffic gets distributed accross then mem partitions usign addr interleaving (crossbar)


* Memory Partition Unit
	+ Contains a portion of L2 cache
	+ Contains a mem access scheduler ("frame buffer")
	+ Note: each mem partition is responsible for an exclusive addr range
	  => L2 cache can be written to and read from (no need for const data only)


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


+------------------------------+
| Instruction Set Architecture |
+------------------------------+


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


+------------------------------+
| Kernel Code Compiler for ISA |
+------------------------------+

+ Will make the assembler
+ Have never built a compiler before, so will be learning it for this project


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


References:
	1. Main one as of now: General-Purpose Graphics Processor Architecture (2018) Book
	   https://link.springer.com/book/10.1007/978-3-031-01759-9

	2. GPGPU-Sim's Manual
	   http://gpgpu-sim.org/manual/index.php/Main_Page