Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl
changeset 0:a5fe730dfc2e
Initial add -- for sourceforge repositories
| author | Me |
|---|---|
| date | Sat, 22 May 2010 19:37:58 -0700 |
| parents | |
| children | cf5007e51b96 |
| files | CoreLoop.c DESIGN_NOTES.txt MasterLoop.c VMS.c VMS.h VMS_primitive_data_types.h |
| diffstat | 6 files changed, 549 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/CoreLoop.c Sat May 22 19:37:58 2010 -0700 1.3 @@ -0,0 +1,62 @@ 1.4 +/* 1.5 + * Copyright 2010 OpenSourceCodeStewardshipFoundation 1.6 + * 1.7 + * Licensed under BSD 1.8 + */ 1.9 + 1.10 + 1.11 + 1.12 + 1.13 + 1.14 +#include "VMS.h" 1.15 +#include "Queue_impl/BlockingQueue.h" 1.16 + 1.17 +#include <stdio.h> 1.18 +#include <time.h> 1.19 + 1.20 + 1.21 +/*This is the loop that runs in the PThread pinned to each core 1.22 + * get work-unit struc from queue, 1.23 + * call function-ptr, passing it pointer to data 1.24 + * transfer return value to slave's "requests" pointer 1.25 + * write the slave's "Done" flag and repeat. 1.26 + */ 1.27 +//pthread_create requires ptr to func that takes void * and returns void * 1.28 +void * coreLoop( void *paramsIn ) 1.29 + { time_t startTime, endTime, timeToExecute; 1.30 + WorkUnit *currWorkUnit; 1.31 + foobar *workFn; 1.32 + SlaveReqst *requestsFromSlave; 1.33 + 1.34 + ThdParams *thdParams; 1.35 + QueueStruc *workQ; 1.36 + 1.37 + // Get the communication queues out of the param passed in 1.38 + thdParams = (ThdParams *)paramsIn; 1.39 + 1.40 + workQ = thdParams -> workQ; 1.41 + 1.42 + // Get to work! 1.43 + while( TRUE ) 1.44 + { 1.45 + // get work-unit struc from queue 1.46 + currWorkUnit = (WorkUnit *) readQ( workQ ); 1.47 + workFn = currWorkUnit->ptrToWorkFunc; 1.48 + 1.49 + time(&startTime); //put time at call into var 1.50 + 1.51 + // call function-ptr, passing it pointer to data 1.52 + requestsFromSlave = 1.53 + (*workFn)( currWorkUnit->workData ); 1.54 + 1.55 + time(&endTime); 1.56 + timeToExecute = endTime - startTime; 1.57 + 1.58 + printf( "timeToComputePiece: %s", ctime(&timeToExecute) ); 1.59 + 1.60 + // transfer return value to slave's "requests" pointer 1.61 + currWorkUnit->slaveAssignedTo->requestsToMaster = requestsFromSlave; 1.62 + // write the slave's "Done" flag and repeat. 1.63 + currWorkUnit->slaveAssignedTo->doneFlag = TRUE; 1.64 + } 1.65 + }
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/DESIGN_NOTES.txt Sat May 22 19:37:58 2010 -0700 2.3 @@ -0,0 +1,40 @@ 2.4 + 2.5 +This project is for a paper -- the goal is to implement and measure the 2.6 + performance of the Virtual Master-Slave system as an alternative to the 2.7 + Thread model. 2.8 + 2.9 +Going to implement exactly one application -- a do-nothing benchmark kernel 2.10 + that just measures scheduling overhead. 2.11 + 2.12 +Implement VMS this way: 2.13 + 2.14 +function to give to PThread that does the loop: 2.15 + 2.16 +get from queue, call function-ptr, passing it work-unit ptr (which contains a 2.17 + pointer to data declared as void * in the application), then write the 2.18 + "Done" flag and repeat. 2.19 + 2.20 + 2.21 +In an application: 2.22 + 2.23 +divide work up into pieces self, just make it a busy-wait loop that writes 2.24 + data, then reads it back, declared volatile. At end of work, call fn that 2.25 + makes a continuation and notifies the Master its there, then return. 2.26 + 2.27 + 2.28 +Master: 2.29 + 2.30 +A loop that polls each virtual slave exactly once, processing each whose 2.31 + Done flag is set, it forces work-units to be one-to-one with slaves, so 2.32 + as soon as done polling slaves, it makes a continuation of itself, puts 2.33 + half the scheduled slaves in, clears its own Done flag, puts its 2.34 + continuation in, the other half of the scheduled slaves, then writes its 2.35 + own Done flag. 2.36 + 2.37 +When continuation first runs, checks if own Done flag set -- if not, busy- 2.38 + waits until set, then proceeds. This ensures it doesn't overlap with 2.39 + tail-end of previous -- IE, continuation may sneak through queue before 2.40 + previous done putting second half of scheduled slaves in. This is the only 2.41 + race condition. 2.42 + 2.43 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/MasterLoop.c Sat May 22 19:37:58 2010 -0700 3.3 @@ -0,0 +1,113 @@ 3.4 +/* 3.5 + * Copyright 2010 OpenSourceCodeStewardshipFoundation 3.6 + * 3.7 + * Licensed under BSD 3.8 + */ 3.9 + 3.10 + 3.11 + 3.12 +#include <stdio.h> 3.13 +#include <malloc.h> 3.14 + 3.15 +#include "VMS.h" 3.16 + 3.17 + 3.18 + 3.19 +/*This code is animated by the virtual Master processor. 3.20 + *Note, it is animated on a different level in virtual processor hierarchy 3.21 + * than the CoreLoop -- this is the code pointed to in a work-unit that the 3.22 + * coreLoop jumps to 3.23 + * 3.24 + *Polls each virtual slave exactly once, hands any requests made by the slave 3.25 + * to the "request handler" plug-in function 3.26 + * 3.27 + *Any slaves that have no work-unit assigned are given to the "schedule" 3.28 + * plug-in function, which tries to assign a work-unit to it. 3.29 + * 3.30 + *When all slaves that need work-units have been given to the schedule plug-in, 3.31 + * half of the ones that were successfully scheduled are put into the work 3.32 + * queue, then a continuation of this function is put in, then the rest of the 3.33 + * slaves that were successfully scheduled. 3.34 + * 3.35 + *The first thing this function does is busy-wait until the previous work-unit 3.36 + * running this function is done. This ensures it doesn't overlap with 3.37 + * tail-end of previous -- IE, continuation may sneak through queue before 3.38 + * previous done putting second half of scheduled slaves in. This is the only 3.39 + * race condition. 3.40 + * 3.41 + */ 3.42 + 3.43 +void masterLoop( void *data ) 3.44 + { bool8 success; 3.45 + int slaveIdx, numScheduled, numInFirstHalf, schedSlaveIdx; 3.46 + VMSProcr currSlave, *virtSlaves; 3.47 + MasterEnv *masterEnv; 3.48 + SlaveScheduler slaveScheduler; 3.49 + RequestHandler requestHandler; 3.50 + 3.51 + 3.52 + masterEnv = (MasterEnv *)data; 3.53 + 3.54 + requestHandler = masterEnv->requestHandler; 3.55 + slaveScheduler = masterEnv->slaveScheduler; 3.56 + virtSlaves = masterEnv->virtSlaves; 3.57 + 3.58 + //if another continuation of Master still running, busy-wait 3.59 + while( masterEnv->stillRunning ) /*busy wait*/ ; 3.60 + 3.61 + //this is the only master running now, set flag again 3.62 + masterEnv->stillRunning = 1; 3.63 + 3.64 + //prepare for scheduling 3.65 + masterEnv->numScheduled = 0; 3.66 + 3.67 + //Poll each slave structure's Done flag 3.68 + for( slaveIdx = 0; slaveIdx < NUM_SLAVES; slaveIdx++) 3.69 + { 3.70 + currSlave = virtSlaves[ slaveIdx ]; 3.71 + 3.72 + if( currSlave->workIsDone ) 3.73 + { 3.74 + currSlave->workIsDone = FALSE; 3.75 + currSlave->needsWorkAssigned = TRUE; 3.76 + 3.77 + //process requests from slave to master 3.78 + (*requestHandler)( currSlave ); 3.79 + } 3.80 + if( currSlave->needsWorkAssigned ) 3.81 + { //give slave a new work-unit 3.82 + success = 3.83 + (*slaveScheduler)( currSlave, masterEnv ); 3.84 + 3.85 + if( success ) 3.86 + { addToVect( currSlave, &(masterEnv->scheduledSlaves), 3.87 + &(masterEnv->numScheduled) ); 3.88 + currSlave->needsWorkAssigned = FALSE; 3.89 + } 3.90 + } 3.91 + } 3.92 + 3.93 + //put half scheduled slaves in, then continuation, then other half 3.94 + VMSProcr **scheduledSlaves; 3.95 + numInFirstHalf = masterEnv->numScheduled / 2; 3.96 + scheduledSlaves = masterEnv->scheduledSlaves; 3.97 + for( schedSlaveIdx = 0; schedSlaveIdx < numInFirstHalf; schedSlaveIdx++) 3.98 + { 3.99 + writeQ( scheduledSlaves[ schedSlaveIdx ], workQ ); 3.100 + } 3.101 + 3.102 + //enqueue continuation of this loop 3.103 + // note that After this enqueue, continuation might sneak through 3.104 + writeQ( masterEnv->masterWorkUnit, workQ ); 3.105 + for( schedSlaveIdx = numInFirstHalf; 3.106 + schedSlaveIdx < numScheduled; 3.107 + schedSlaveIdx++) 3.108 + { 3.109 + writeQ( scheduledSlaves[ schedSlaveIdx ]->workUnitToDo, workQ ); 3.110 + } 3.111 + 3.112 + //all done, so okay for continuation to proceed 3.113 + masterEnv->stillRunning = 0; 3.114 + } 3.115 + 3.116 +
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 4.2 +++ b/VMS.c Sat May 22 19:37:58 2010 -0700 4.3 @@ -0,0 +1,176 @@ 4.4 +/* 4.5 + * Copyright 2010 OpenSourceCodeStewardshipFoundation 4.6 + * 4.7 + * Licensed under BSD 4.8 + */ 4.9 + 4.10 +#include <stdio.h> 4.11 +#include <stdlib.h> 4.12 +#include <malloc.h> 4.13 + 4.14 +#include "VMS.h" 4.15 +#include "Queue_impl/BlockingQueue.h" 4.16 + 4.17 + 4.18 +/*Setup has two phases: 4.19 + * 1) Semantic layer first calls init_VMS, which creates masterEnv, and puts 4.20 + * the master work-unit into the work-queue 4.21 + * 2) Semantic layer then does its own init, which creates the initial 4.22 + * work-units inside the semantic layer, ready to schedule them when 4.23 + * asked by the first run of the masterLoop. 4.24 + * 4.25 + *This part is bit weird because VMS really wants to be "always there", and 4.26 + * have applications attach and detach.. for now, this VMS is part of 4.27 + * the app, so the VMS system starts up as part of running the app. 4.28 + * 4.29 + *The semantic layer is fully isolated from the VMS internasl by 4.30 + * making the semantic layer setup into a state that it's ready with its 4.31 + * initial work-units, ready to schedule them to slaves when the masterLoop 4.32 + * asks. Without this pattern, the semantic layer's setup would 4.33 + * have to modify slaves directly to assign the initial work-units, and put 4.34 + * them into the workQ itself, breaking the isolation completely. 4.35 + * 4.36 + * 4.37 + *The semantic layer creates the initial work-unit(s), and adds its 4.38 + * own environment data to masterEnv, and fills in the pointers to 4.39 + * the requestHandler and slaveScheduler plug-in functions 4.40 + * 4.41 + *This allocates VMS data structures, populates the master VMSProc, 4.42 + * and master environment, and returns the master environment to the semantic 4.43 + * layer. 4.44 + */ 4.45 + //Global vars are all inside VMS.h 4.46 +MasterEnv * 4.47 +init_VMS( ) 4.48 + { 4.49 + //Make the central work-queue 4.50 + workQ = makeQ(); 4.51 + 4.52 + masterEnv = malloc( sizeof(MasterEnv) ); 4.53 + 4.54 + create_master( masterEnv ); 4.55 + 4.56 + create_slaves( masterEnv ); 4.57 + 4.58 + //When coreLoops start up, the first thing 4.59 + writeQ( masterEnv->masterWorkUnit, workQ ); 4.60 + } 4.61 + 4.62 + 4.63 + 4.64 +/*Fill up the virtual master data structure, which is already alloc'd in the 4.65 + * masterEnv. 4.66 + *The virtual Master is the same structure as a virtual slave, but it 4.67 + * isn't in the array of virtual slaves. 4.68 + * The reason it's the same structure is so that the coreLoop doesn't 4.69 + * have to differentiate -- all work units are assigned to a VMSProcr, and 4.70 + * the core loop treats them all the same way, whether it's the virtual 4.71 + * master continuation or a slave's work-unit. 4.72 + *Note: masterLoop is jumped into an back out of, so have to be careful with 4.73 + * register usage and saving all persistent-across-calls state to masterEnv 4.74 + */ 4.75 +void 4.76 +create_master( MasterEnv *masterEnv ) 4.77 + { VMSProcr virtMaster; 4.78 + 4.79 + virtMaster = &(masterEnv->virtMaster); 4.80 + virtMaster->workUnitToDo = malloc( sizeof( WorkUnit ) ); 4.81 + virtMaster->workUnitToDo->workData = masterEnv; 4.82 + //TODO: figure out call structure: what GCC will do with regs 4.83 + // will jump to the masterLoop from the coreLoop -- what regs need 4.84 + // saving, from before jump to after -- and what reg to put masterEnv 4.85 + // pointer in when jump to masterLoop 4.86 + virtMaster->workUnitToDo->addrToJumpTo = &masterLoop; 4.87 + virtMaster->workUnitToDo->slaveAssignedTo = virtMaster; 4.88 + } 4.89 + 4.90 +void 4.91 +create_slaves( MasterEnv *masterEnv ) 4.92 + { VMSProcr *virtSlaves; 4.93 + int i; 4.94 + 4.95 + virtSlaves = masterEnv->virtSlaves; //TODO: make sure this is right 4.96 + for( i = 0; i < NUM_SLAVES; i++ ) 4.97 + { 4.98 + //Set state to mean "everything done, schedule work to slave" 4.99 + virtSlaves[i].workIsDone = FALSE; 4.100 + virtSlaves[i].needsWorkAssigned = TRUE; 4.101 + } 4.102 + } 4.103 + 4.104 +/*Semantic layer calls this when it want the system to start running.. 4.105 + * 4.106 + *This creates the core loops, pins them to physical cores, gives them the 4.107 + * pointer to the workQ, and starts them running. 4.108 + */ 4.109 + void 4.110 +VMS__start() 4.111 + { int retCode, coreIdx; 4.112 + 4.113 +//TODO: still just skeleton code -- figure out right way to do this 4.114 + 4.115 + //Create the PThread loops that take from work-queue, and start them 4.116 + for( coreIdx=0; coreIdx < NUM_WORKERS; coreIdx++ ) 4.117 + { 4.118 + thdParams[coreIdx] = (ThdParams *)malloc( sizeof(ThdParams) ); 4.119 + thdParams[coreIdx]->workQ = workQ; 4.120 + thdParams[coreIdx]->id = coreIdx; 4.121 + 4.122 + //Now make and start thd.. the coreLoopThds entry 4.123 + // has all the info needed to later stop the thread. 4.124 + retCode = 4.125 + pthread_create( &(coreLoopThds[coreIdx]), thdAttrs, &coreLoop, 4.126 + (void *)(thdParams[coreIdx]) ); 4.127 + if( retCode != 0 ) 4.128 + { //error 4.129 + printf("ERROR creating coreLoop %d, code: %d\n", coreIdx, retCode); 4.130 + exit(-1); 4.131 + } 4.132 + 4.133 + pinThdToCore( ); //figure out how to specify this.. 4.134 + 4.135 + startThd(); //look up PThread call to start the thread running, if it's 4.136 + // not automatic 4.137 + } 4.138 + } 4.139 + 4.140 + /*there is a label inside this function -- save the addr of this label in 4.141 + * the callingPr struc, as the pick-up point from which to start the next 4.142 + * work-unit for that procr. If turns out have to save registers, then 4.143 + * save them in the procr struc too. Then do assembly jump to the CoreLoop's 4.144 + * "done with work-unit" label. The procr struc is in the request in the 4.145 + * slave that animated the just-ended work-unit, so all the state is saved 4.146 + * there, and will get passed along, inside the request handler, to the 4.147 + * next work-unit for that procr. 4.148 + */ 4.149 +VMS__save_ret_and_jump_to_CoreLoop( callingPr ) 4.150 + { 4.151 + //TODO: figure out how to save the addr of a label into a mem loc 4.152 + //NOTE: because resume pt is inside the VMS fn, it's always the same, no 4.153 + // matter what the semantic layer is, no matter what semantic libr called. 4.154 + callingPr->resumePt = &resumeNextWorkUnitPt; 4.155 + save_processor_state_in( callingPr ); //save x86 regs, if GCC needs it to 4.156 + coreLoopRetPt = callingPr->coreLoopRetPt; 4.157 + //TODO: figure out how to do jump correctly -- target addr is constant 4.158 + asm( jmp coreLoopRetPt ); 4.159 + 4.160 +resumeNextWorkUnitPt: 4.161 + return; 4.162 + } 4.163 + 4.164 + 4.165 +/*The semantic virt procr is available in the request sent from the slave 4.166 + * 4.167 + * The request handler has to add the work-unit created to the semantic 4.168 + * virtual processor the work-unit is a section of its time-line -- does this when create the 4.169 + * work-unit -- means the procr data struc is available in the request sent 4.170 + * from the slave, from which the new work-unit is generated.. 4.171 + */ 4.172 +VMS__add_request_to_slave( SlaveReqst req, VMSProcr callingPr ) 4.173 + { VMSProcr slave; 4.174 + slave = callingPr->workUnit->currSlave 4.175 + req->nextRequest = callingPr->workUnit->currSlave->requests = req; 4.176 + } 4.177 + 4.178 + 4.179 +
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/VMS.h Sat May 22 19:37:58 2010 -0700 5.3 @@ -0,0 +1,105 @@ 5.4 +/* 5.5 + * Copyright 2009 OpenSourceStewardshipFoundation.org 5.6 + * Licensed under GNU General Public License version 2 5.7 + * 5.8 + * Author: seanhalle@yahoo.com 5.9 + * 5.10 + */ 5.11 + 5.12 +#ifndef _VMS_H 5.13 +#define _VMS_H 5.14 + 5.15 + 5.16 +#include "VMS_primitive_data_types.h" 5.17 +#include "Queue_impl/BlockingQueue.h" 5.18 + 5.19 +//This value is the number of hardware threads in the shared memory 5.20 +// machine 5.21 +#define NUM_WORKERS 4 5.22 +#define NUM_SLAVES 8 5.23 + 5.24 +#define SUCCESS 0 5.25 + 5.26 +#define thdAttrs NULL 5.27 + 5.28 +typedef struct WorkUnit WorkUnit; 5.29 +typedef struct VMSProcr VMSProcr; 5.30 +typedef struct SlaveReqst SlaveReqst; 5.31 + 5.32 +typedef bool8 (*SlaveScheduler) ( void * ); 5.33 +typedef void (*RequestHandler) ( SlaveReqst * ); 5.34 + 5.35 +typedef struct 5.36 + { 5.37 + QueueStruc *workQ; 5.38 + unsigned int id; 5.39 + } 5.40 +ThdParams; 5.41 + 5.42 +//This is application-level data of the scheduler that runs in the master 5.43 +// virtual processor. This data is at a higher level than the slave data- 5.44 +// struc, which is part of the virtualization infrastructure.. this 5.45 +// MasterEnv sits on top of that level 5.46 +typedef struct 5.47 + { 5.48 + VMSProcr virtSlaves[ NUM_SLAVES ]; 5.49 + VMSProcr virtMaster; 5.50 + 5.51 + SlaveScheduler slaveScheduler; 5.52 + RequestHandler requestHandler; 5.53 + 5.54 + int stillRunning; 5.55 + WorkUnit *masterWorkUnit; 5.56 + 5.57 + VMSProcr **scheduledSlaves; 5.58 + int numScheduled; 5.59 + 5.60 + void *OSEventStruc; 5.61 + void *semanticEnv; 5.62 + } 5.63 +MasterEnv; 5.64 + 5.65 + 5.66 +struct WorkUnit 5.67 + { 5.68 + VMSProcr *slaveAssignedTo; 5.69 + void *addrToJumpTo; 5.70 + void *workData; 5.71 + 5.72 + void *pluginSpecific; 5.73 + }; 5.74 + 5.75 + 5.76 +struct VMSProcr 5.77 + { 5.78 + WorkUnit *workUnitToDo; 5.79 + SlaveReqst *requestsToMaster; 5.80 + int workIsDone; 5.81 + int needsWorkAssigned; 5.82 + }; 5.83 + 5.84 +struct SlaveReqst 5.85 + { 5.86 + VMSProcr *slaveFrom; 5.87 + int reqType; 5.88 + void *reqData; 5.89 + 5.90 + SlaveReqst *nextRequest; 5.91 + }; 5.92 + 5.93 + 5.94 + 5.95 +void * coreLoop( void *paramsIn ); //standard PThreads fn prototype 5.96 + 5.97 + 5.98 +//===================== Global Vars =================== 5.99 + 5.100 +pthread_t coreLoopThds[ NUM_WORKERS ]; // std struc, holds thread info 5.101 +QueueStruc *workQ; 5.102 +ThdParams thdParams[ NUM_WORKERS ]; 5.103 + 5.104 +MasterEnv *masterEnv; 5.105 + 5.106 + 5.107 +#endif /* _VMS_H */ 5.108 +
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 6.2 +++ b/VMS_primitive_data_types.h Sat May 22 19:37:58 2010 -0700 6.3 @@ -0,0 +1,53 @@ 6.4 +/* 6.5 + * Copyright 2009 OpenSourceStewardshipFoundation.org 6.6 + * Licensed under GNU General Public License version 2 6.7 + * 6.8 + * Author: seanhalle@yahoo.com 6.9 + * 6.10 + 6.11 + */ 6.12 + 6.13 +#ifndef _BLIS_PRIMITIVE_DATA_TYPES_H 6.14 +#define _BLIS_PRIMITIVE_DATA_TYPES_H 6.15 + 6.16 + 6.17 +/*For portability, need primitive data types that have a well defined 6.18 + * size, and well-defined layout into bytes 6.19 + *To do this, provide BLIS standard aliases for all primitive data types 6.20 + *These aliases must be used in all BLIS functions instead of the ANSI types 6.21 + * 6.22 + *These definitions will be replaced inside each specialization module 6.23 + * according to the compiler used in that module and the hardware being 6.24 + * specialized to. 6.25 + */ 6.26 +/* 6.27 +#define int8 char 6.28 +#define uint8 char 6.29 +#define int16 short 6.30 +#define uint16 unsigned short 6.31 +#define int32 int 6.32 +#define uint32 unsigned int 6.33 +#define int64 long long 6.34 +#define uint64 unsigned long long 6.35 +#define float32 float 6.36 +#define float64 double 6.37 +*/ 6.38 +typedef char bool8; 6.39 +typedef char int8; 6.40 +typedef char uint8; 6.41 +typedef short int16; 6.42 +typedef unsigned short uint16; 6.43 +typedef int int32; 6.44 +typedef unsigned int uint32; 6.45 +typedef long long int64; 6.46 +typedef unsigned long long uint64; 6.47 +typedef float float32; 6.48 +typedef double float64; 6.49 +//typedef double double float128; 6.50 +#define float128 double double 6.51 + 6.52 +#define TRUE 1 6.53 +#define FALSE 0 6.54 + 6.55 +#endif /* _BLIS_PRIMITIVE_DATA_TYPES_H */ 6.56 +
