Functional (Task) Decomposition
Mike Bailey
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
Computer Graphics
Copyright By PowCoder代写 加微信 powcoder
functional_decomposition.pptx
mjb – March 10, 2022
The Functional (or Task) Decomposition Design Pattern
erall Problem
Computer Graphics
A good example of this is the computer game SimPark.
mjb – March 10, 2022
Computer Graphics
The Functional (or Task) Decomposition Design Pattern
Credit: Maxis (Sim Park)
mjb – March 10, 2022
How is this is different from Data Decomposition (such as the OpenMP for-loops)
• This is done less for performance and more for programming convenience.
• This is often done in simulations, where each quantity in the simulation needs to make decisions about what it does next based on what it and all the other quantities are doing right now.
• Each quantity takes all of the “Now” state data and computes its own “Next” state.
• The biggest trick is to synchronize the different quantities so that each of them is seeing only what the others’ data are right now. Nobody is allowed to switch their data states until they are all done consuming the current data and thus are ready to switch together.
• The synchronization is accomplished with barriers.
Quantity #1:
Complete Now State
Individual Next State Computer Graphics
Quantity #2:
Complete Now State Compute Individual Next State
Quantity #3:
Complete Now State
Individual Next State
mjb – March 10, 2022
Setup the Now global variables Calculate the current Environmental Parameters
Spawn Threads using OpenMP Sections
Using the entire Now state, compute A’s Next variables
DoneComputing barrier
Using the entire Now state, compute B’s Next variables
Copy A’s Next state into the Now state
Copy B’s Next state into the Now state
DoneAssigning barrier
Print results and increment time
Calculate new Environmental Parameters
DonePrinting barrier
Computer Graphics
mjb – March 10, 2022
The Functional Decomposition Design Pattern
main( int argc, char *argv[ ] ) {
omp_set_num_threads( 3 );
InitBarrier( 3 );
#pragma omp parallel sections
// don’t worry about this for now, we will get to this later
Computer Graphics
#pragma omp section
Watcher( );
#pragma omp section
Animals( );
#pragma omp section
Plants( );
} // implied barrier — all functions must return to get past here
mjb – March 10, 2022
The Functional Decomposition Design Pattern
void Watcher( ) {
while( << You decide how to know when finished? >> ) {
// do nothing
WaitBarrier( ); // 1.
// do nothing
WaitBarrier( ); // 2.
<< write out the “Now” state of data >>
<< advance time and re-compute all environmental variables >>
WaitBarrier( ); // 3.
Computer Graphics
mjb – March 10, 2022
The Functional Decomposition Design Pattern
Computer Graphics
void Animals( ) {
while( << You decide how to know when finished? >> ) {
int nextXXX= << function of what all states are right Now >> …
WaitBarrier( );
NowXXX = nextXXX;
WaitBarrier( );
// do nothing
WaitBarrier( );
// copy the computed next state to the Now state
// 2. // 3.
mjb – March 10, 2022
My Simulation Output
Temperature
Computer Graphics
mjb – March 10, 2022
You Might Have to Make Your Own Barrier Function
Why can’t we just use #pragma omp barrier ?
The Functional Decomposition is a good example of when you sometimes can’t.
There are two ways to think about how to allow a program to use a barrier:
1. Let the barrier happen at a specific location in the code
2. Let the barrier work after a specific number of threads have gotten there
• g++ allows both #1 and #2
• Visual Studio requires #1
• The Functional Decomposition shown here wants to have #2,
because the barriers need to be in different functions
Computer Graphics
mjb – March 10, 2022
Computer Graphics
Sometimes You Have to Make Your Own Barrier Function
omp_lock_t Lock;
int NumInThreadTeam; int NumAtBarrier;
int NumGone;
InitBarrier( int n ) {
NumInThreadTeam = n; NumAtBarrier = 0; omp_init_lock( &Lock );
void WaitBarrier( ) {
omp_set_lock( &Lock );
NumAtBarrier++;
if( NumAtBarrier == NumInThreadTeam ) {
NumGone = 0;
NumAtBarrier = 0;
// let all other threads return before this one unlocks: while( NumGone != NumInThreadTeam – 1 ); omp_unset_lock( &Lock );
omp_unset_lock( &Lock );
while( NumAtBarrier != 0 );
#pragma omp atomic
// all threads wait here until the last one arrives … // … and sets NumAtBarrier to 0
// number of threads you want to block at the barrier
// release the waiting threads
NumGone++;
mjb – March 10, 2022
The WaitAtBarrier( ) Logic
Computer Graphics
mjb – March 10, 2022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com