1CS267 L9 Split-C Programming.1Demmel Sp 1999CS 267 Applications of Parallel ComputersLecture 9: Split-CJames Demmelhttp://www.cs.berkeley.edu/~demmel/cs267_Spr99CS267 L9 Split-C Programming.2Demmel Sp 1999Comparison of Programming Models° Data Parallel (HPF)• Good for regular applications; compiler controls performance° Message Passing SPMD (MPI)• Standard and portable• Needs low level programmer control; no global data structures° Shared Memory with Dynamic Threads• Shared data is easy, but locality cannot be ignored• Virtual processor model adds overhead° Shared Address Space SPMD• Single thread per processor• Address space is partitioned, but shared• Encourages shared data structures matched to the architecture• Titanium - targets (adaptive) grid computations• Split-C - simple parallel extension to C° F77 + Heroic Compiler• Depends on compiler to discover parallelism• Hard to do except for fine grain parallelism, usually in loops2CS267 L9 Split-C Programming.3Demmel Sp 1999Overview of Split-C° Parallel systems programming language based on C° Can run on most machines° Creating Parallelism: SPMD° Memory Model• Shared address space via global pointers and spread arrays° Split phase communication° Examples and Optimization opportunitiesCS267 L9 Split-C Programming.4Demmel Sp 1999SPMD Control ModelPEPEPEPEPEPEPEPEPROCS threads of control° independent° explicit synchronizationSynchronization° global barrier° locksbarrier();3CS267 L9 Split-C Programming.5Demmel Sp 1999Recall C Pointers° (&x) read ‘pointer to x’° Types read right to leftint * read as ‘pointer to int’° *P read as ‘value at P’/* assign the value of 6 to x */int x;int *P = &x;*P = 6;int x0xC000 ???int *P0xC004 0xC000Address Valueint x0xC000 6int *P0xC004 0xC000Address ValueCS267 L9 Split-C Programming.6Demmel Sp 1999Global Pointersint *global gp1; /* global ptr to an int */typedef int *global g_ ptr;gptr gp2; /* same */typedef double foo;foo *global *global gp3; /* global ptr to a global ptr to a foo*/int *global *gp4; /* local ptr to a global ptr to an int*/A global pointer may refer to anobject anywhere in the machine.global ptr = (proc#, local ptr)Each object (C structure) pointedto lives on one processorGlobal pointers can bedereferenced, incremented, andindexed just like local pointers.PEPEPEPEPEPEPEPEgp34CS267 L9 Split-C Programming.7Demmel Sp 1999Memory Modelon_one {double *global g_P =toglobal(2,&x);*g_P = 6;}Processor 0Processor 2Address Valueint x0xC000 ???int *g_P0xC004 ???int x0xC000 ???int *g_P0xC004 2 , 0xC000Address Valueint x0xC000 6int *g_P0xC004 ???CS267 L9 Split-C Programming.8Demmel Sp 1999What can global pointers point to?° Anything, but not everything is useful° Global heap (all_spread_malloc)• Space guaranteed to occupy same addresses on all processorsso one pointer points to same location relative to base on allprocessors° Spread Arrays (coming next)° Data in stack• Dangerous: After routine returns, pointer no longer points to validaddress• Ok if all processors at same point in call tree5CS267 L9 Split-C Programming.9Demmel Sp 1999Recall C Arrays° Set 4 values to 0,2,4,6° Origin is 0for (i = 0; i< 4; i++) {A[i] = i*2;}° Pointers & Arrays:• A[i] == *(A+i)A0246A+1A+2A+3CS267 L9 Split-C Programming.10Demmel Sp 1999Spread Arrays in Split-CSpread Arrays are spread over the entire machine– spreader “::” determines which dimensions are spread– dimensions to the right define the objects on individualprocessors– dimensions to the left are linearized and spread in cyclicmapExample 1: double A[PROCS]::[10],Per processor blocksSpread high dimensionsExample 2: double A[n][r]::[b][b] A[i][j] is a b-by-b block living on processor i*r + j mod PThe traditional C duality between arrays and pointers is preservedthrough spread pointers.A[i][j] is j-th word on processor
View Full Document
Unlocking...