Top Up Prev Next Bottom Contents Index Search

18.1 Buffer Allocation


In the CGC domain, we allocate one buffer for each connection in principle. We have to determine the required size of buffers first. If a porthole is embedded , and the buffer size requirement is equal to the sample rate of the embedded port, we do NOT allocate a buffer on that connection. We will use static buffering for all embedded and embedding portholes. If the buffer requirement of an embedded(or embedding) porthole is not equal to the sample rate of the porthole, we actually need to have two buffers on that connection and copy data between these buffers. In this case, we splice a Copy star on the arc and schedule the Copy star appropriately to generate code for copying data. After inserting the Copy star, we will end up with one buffer per connection. Another cause of copy requirement is type conversion from complex to float/int or from float/int to complex. Then, we splice a type-conversion star on the arc.

Class CGCTarget redefines the following protected method for buffer allocation .

int allocateMemory(); 
In this method, we first merge cascaded forks into a single fork whose input keeps the list of all fork destinations. We will allocate only one buffer for each fork. All fork destinations will refer to the same fork input buffer. Then this method does the following tasks:

1. Determine the buffer requirements for all portholes.

2. Splice Copy stars or type conversion stars if necessary.

3. Set the buffer type for each output porthole: either OWNER or EMBEDDED. If the output porthole is embedded, or the corresponding input porthole is embedded, it is called EMBEDDED. Otherwise, it is OWNER. The buffer type of an output is determined using the following public method of CGCPortHole class:

void setBufferType(); 
4. We assign unique names for buffers.

5. We initialize the offset pointer for each porthole which is associated with a buffer of size greater than 0 (initOffset method of CGCPortHole class). This offset pointer indicates from which offset of the buffer the porthole starts reading or writing samples.

int initOffset(); 
This is a public method of CGCPortHole class to initialize the offset pointer. If there are delays, or initial samples, on the arc, these samples are placed at the end of the buffer. The offset pointer of a porthole indicates the location of the last sample the next firing of its parent star will produce or consume. It is compatible with the SDF simulation domain: $ref(porthole,num) in CGC stars is now equivalent to porthole%num in SDF stars. We can set the offset pointer of an output porthole manually by the following public method of CGCPortHole class.

void setOffset(int v); 
Now, we will explain steps (1), (2), and (4) in more detail.

18.1.1 Buffer requirement

To determine the buffer requirements of portholes, we traverse portholes of all stars, and call finalBufSize method of CGCPortHole class.

void finalBufSize(int statBuf); 
This is a public method of CGCPortHole class to determine the buffer size for this porthole. The argument indicates whether we try to use static buffering or not. We allocate one buffer for each connection. Therefore, we do nothing if this porthole is an input porthole. If this porthole is disconnected, we set the buffer size equal to the number of samples produced for each firing. If it lies at wormhole boundary, we use localBufSize method of CGPortHole class to determine the size of buffer and return. Otherwise, we do the following:

1. We can manually assign the buffer size by calling requestBufSize for an output porthole of interest in the setup stage of a star:

void requestBufSize(int sz); 
This method sets the buffer size manually. The argument size should not be smaller than the minimum size determined by the scheduler. The minimum size determined by the scheduler is the sum of maximum number of samples accumulated on the arc during the schedule and the number of old samples to be access from the destination port. If sz is smaller than this minimum value, we generate a warning message and give up manual allocation.

2. We set the initial buffer size by calling localBufSize method of CGPortHole class. If argument statBuf = 1, we set the buffer size as a smallest multiple of the sample rate of this porthole, which is not less than the initial buffer size. By doing this, we increase the chance of using linear buffering. We also set the waste factor in CGCGeodesic class to a huge number by calling the following public method in CGCGeodesic class:

void preferLinearBuf(int i) 
The waste factor set by the above method can be obtained by the following redefined protected method of the CGCGeodesic class.

double wasteFactor() const; 
3. We set two flags for this porthole to indicate we can use static buffering and/or linear buffering: hasStaticBuf and asLinearBuf. These two flags are all private. If static buffering flag is set, we use direct addressing in the generated code to access the buffer. If linear buffering flag is set, we will use indirect addressing and no modulo addressing will be required. Otherwise, we will use indirect addressing and modulo addressing in the generated code to access the allocated buffer. Initially both flags are set TRUE. If this porthole needs to access past samples, we reset both flags to FALSE. When the argument statBuf is given 0, we give up static buffering in case the buffer size determined in (2) is greater than the sample rate of this porthole. Note that if a loop scheduler is used, statBuf becomes 0 and some possibilities of static buffering are sacrificed as the cost of code compaction. The following method is called to adjust the flags further.

void setFlags(); 
Is a protected member of CGCPortHole class. If the final buffer size is not a multiple of the sample rate, we reset asLinearBuf flag to 0. We have to use modulo addressing in the generated code. If the product of the sample rate and the repetition count of its parent star is not a multiple of the final buffer size, we give up static buffering, setting hasStaticBuf to 0. If an output porthole is embedded or embedding, we set both flags TRUE since we enforce static buffering.

4. As the final step, we set the flags for destination portholes. If this porthole is connected to a fork input, all fork destinations will be the destination portholes of this porthole. We first check whether statBuf argument is 0 and the buffer size is greater than the sample rate of the porthole. And, we call setFlags method for that porthole. If the porthole needs to access past samples, or the number of initial samples on the connection is not a multiple of the sample rate, we give up linear buffering.

The final buffer size can be obtained by the following two public methods of CGCPortHole class.

int maxBufReq() const; 
int bufSize() const { return maxBufReq(); }
The above methods return the final buffer size associated with this porthole. If it is a fork destination, it returns the size of the fork input buffer. If the porthole has switched its Geodesic , it returns the size of buffer associated with the switched Geodesic.

The flags for static buffering and linear buffering can be obtained by the following public methods of CGCPortHole class:

int linearBuf() const;
int staticBuf() const;
We give up static buffering for a CGPortHole by calling the following public method of CGCPortHole class.

void giveUpStatic(); 

18.1.2 Splice stars

After buffer requirements for all portholes are determined, we can detect the arcs which can not have only one buffer. For instance, if we need to convert data types from complex to float/int or vice versa automatically, we need two buffers on the arc: one for complex variables and the other for float/int variables. This copying operation is required since C language does not provide built-in "complex" type variable. Therefore, we define "complex" type data in the generated code as follows;

static char* complexDecl = 
"\back n#if !defined(COMPLEX_DATA)\back n#define COMPLEX_DATA 1"
"\back n typedef struct complex_data { double real; double imag; } complex; \back n"
"#endif\back n";
Another case is when an embedded or embedding porthole requires a buffer whose size is greater than the sample rate of the porthole. Recall that an embedded or embedding porthole will assume static buffering for each execution when we generate code for that porthole. If the buffer size is larger than the sample rate, we may not use static buffering. We need two buffers for the embedded or embedding porthole.

Rather than assigning two buffers on an arc and letting the target generating code to copy data between these two buffers, we splice a star on the arc. The spliced star will separate two buffers on one arc into one buffer on its input and the other buffer on its output arc. When this spliced star is scheduled before the destination star of after the source star, it will generate code to copy data from the input buffer to the output buffer.

Stars are spliced in the following protected method of CGCTarget class.

void addSpliceStars(); 
This method traverses all portholes of stars in the galaxy.

When we splice a star at an input porthole (destination porthole), we initialize the spliced star and set the target pointer. A spliced star should have one "input" and one "output". We set the sample rate of these portholes equal to the sample rate of the input porthole. The buffer size of the input porthole of the spliced star is determined by the original source porthole. The buffer size of the output porthole is set the sample rate of the input porthole. And, we check whether static or linear buffering can be used for the portholes. The input porthole of a spliced Copy star gives up static buffering while the output porthole of the spliced Copy star and the original destination porthole can use static and linear buffering. In case we spliced a type conversion star, we need to change the type of the original source porthole.

We splice a Copy star at the output (source porthole) when the output is an embedded or embedding porthole and the buffer size is larger than the sample rate of the output porthole. We initialize the spliced star and set the target pointer. The sample rate of the input and output porthole of the spliced Copy star is equal to the sample rate of the output porthole. The buffer size of the output porthole of the spliced star is set to the buffer size of the arc. We give up static buffering for this output porthole. On the other hand, we change the buffer size of the source porthole to the sample rate of the porthole.

We need to pay special attention to Collect (or Spread) stars. A Collect (or Spread) star is not a regular SDF star so that it is not scheduled when all input data are available. Actually, we do not execute the spliced Collect (or Spread) stars. But, the output porthole of a Collect (or Spread) star is an embedding (or embedded) porthole. And its buffer size can be larger than the sample rate of the porthole. In this case, we splice a Copy star at the destination porthole, not at the source porthole. We schedule this Copy star before the destination star. The sample rate of portholes of the spliced Copy star is equal to the sample rate of the destination porthole. The output buffer size of the spliced star is set the the buffer size of the arc while the input buffer size now becomes the sample rate of the source porthole. The trickest part here is to determine the offset pointers. We copy data when the destination porthole requires it. Therefore, the offset pointers of the input porthole and the output porthole of the spliced Copy star depends on the initial delay on the arc. We manually set the offset by setOffset method of CGCPortHole class.

There is another case we need data copying between two buffers: when two embedded portholes are connected together. Suppose, an output porthole of a Spread star is connected to an input porthole of a Collect star. Since the output porthole of a Spread star is embedded to the input buffer and the input porthole of a Collect star is embedded to the output buffer, we need to copy data from the input buffer of the Spread star to the output buffer of the Collect star. Since we do not schedule neither Spread nor Collect star, we may not splice a Copy star either at the source porthole not at the destination porthole. Therefore, we leave it as a special case so that we generate code to copy data between two buffers in moveDataBetweenShared method of CGCStar class after executing the star connected to the input porthole of the Spread star. So, we do not splice star when two embedded portholes are connected together.

void moveDataBetweenShared(); 
This is a protected method of CGCStar class. This method is called inside runIt method after generating code for a star. If the star is connected to an embedding porthole of a star of which an embedded output porthole is connected to an embedded porthole. Since we meet the case when two embedded portholes are connected, we generate code for copying data between two embedding buffers.

Scheduling spliced stars

When we splice a star at the input port of a star, we want to schedule the spliced star before the star. On the other hand, we want to schedule the spliced star after a star if we splice a star at the output porthole of the star. When we splice stars, we are already given the schedule. Therefore, we need to insert spliced stars into the schedule. An intuitive approach is to insert them into the schedule list.

Currently, we use a simpler method. We use the fact that the spliced star and the star connected to the spliced star can be regarded as a cluster and schedule of that cluster is well known. Our idea is to actually execute the cluster when we execute a star if the star is connected to spliced stars. CGCStar class has a private member to keep the list of stars: spliceClust. Initially, the star itself is inserted to the list. If we splice a star at the input porthole, we prepend the spliced star to the list. If we splice a star at the output porthole, we append the spliced star to the list. And, we redefine run method.

int run(); 
If there are spliced stars, or the list size is greater than 1, we traverse the list and execute runIt method for each star. Otherwise, we execute runIt method.

int runIt(); 
It is a protected method of CGCStar class to generate main code for this star. If generates a comment regarding this star and main code. It updates offset pointers of the star. Finally, it calls moveDataBetweenShared method to generate code to copy data between two embedding portholes if necessary.

18.1.3 Buffer naming

One major task for resource assignment in the CGC domain is to give a unique name for each variable. In the setup stage of the CGCTarget, we assign a unique index value to each star starting from 1 to the number of stars in the galaxy. The CGCTarget has two protected members to give a unique index for galaxy.

int galId; 
int curId;
The second member is used to give unique indices for galaxies while the first member indicates the index of the current galaxy.

Now, the CGCTarget can generate a unique name for each variable, portholes and states, by the following protected method.

StringList sanitizedFullName(const NamedObj& b) const; 
In this method, the argument object is a porthole or a state of a star. We prefix 'g' followed by the galaxy index, followed by "_", followed by the name of the star, followed by another '_', followed by the star index, followed by yet another '_' to the name of the object. For example, if star A has a state xx and the star index is 2 and the galaxy index is 1, the name of the state becomes "g1_A_2_xx".

StringList correctName(const NamedObj& b); 
Is a public version of sanitizedFullName method.

Now, we are ready to generate unique names for portholes.

void setGeoName(char* name); 
Is a public method of CGCPortHole class. If this porthole is disconnected and no Geodesic is assigned, we store the name in the porthole. Otherwise, we store the name in the Geodesic by calling the following public method of CGCGeodesic class.

void setBufName(char* name); 
The buffer name of a porthole can be obtained by the following public method of CGCPortHole class.

const char* getGeoName() const; 
This method returns the buffer name stored in this object if it is disconnected, or call getBufName method of CGCGeodesic class. If it is a fork destination, it returns the name of the fork input buffer.



Top Up Prev Next Bottom Contents Index Search

ptolemy@eecs.berkeley.edu
Copyright © 1990-1997, University of California. All rights reserved.