SPO600 – Lab 5 -Algorithm Selection

The purpose of this lab was to construct two approaches to adjusting the volume of a sequence of sound samples, using different algorithms, in the C language. We first created an array of 500000000 signed int16 to be our container for the sound samples. The values would range from 32768 to 32767.

We decided upon two approaches to this problem.

Naive Approach

The first approach was to create a naive version of the code where the value was in the sound sample array was simply multiplied by a given volume scale factor and storing back into self.

Lookup Table Approach

The second approach was to use a look up table which had all of the possible values for that volume scale factor pre-calculated into an array.

Full Code

#include 
#include 
#include <sys/time.h>
#include 
#define MAXSAMPLES 500000000
#define VOLUMESCALEFACTOR 0.5
#define MAXVALUE 32768

//simulate an audio file
void generateSamples(int16_t* soundSample) {
 int i;
 for(i = 0; i <= MAXSAMPLES; i++) {
 soundSample[i] = rand() % MAXVALUE;
 }
}

//multiply and store back into array
void naiveApproach(int16_t* soundSample) {
 int i;
 for (i = 0; i <= MAXSAMPLES; i++) {
 soundSample[i] = soundSample[i] * VOLUMESCALEFACTOR;
 }
}

//generate a lookup table of pre-calculated values
void generateLookUp(int16_t* lookUpTable) {
 int i;
 for(i = 0; i <= MAXVALUE; i++) {
 lookUpTable[i] = i * VOLUMESCALEFACTOR; 
 }
}

void useLookUp(int16_t* soundSample, int16_t* lookUpTable) {
 int i;
 for(i = 0; i <= MAXSAMPLES; i++) {
 soundSample[i] = lookUpTable[soundSample[i]]; 
 }
}

int main() {
 //time variables
 struct timeval t1, t2;
 double timeElapsedMSec;
 
 //allocate an array of signed integers of 500000000 and generate values
 int16_t* soundSample = (int16_t*) malloc(sizeof(int16_t) * MAXSAMPLES);
 generateSamples(soundSample);
 
 gettimeofday(&t1, NULL);
 naiveApproach(soundSample);
 gettimeofday(&t2, NULL);
 
 timeElapsedMSec = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
 printf("Naive Approach\n");
 printf("timeElapsedMSec: %f\n", timeElapsedMSec);

//allocate an array of 32768 signed integers
 int16_t* lookUpTable = (int16_t*) malloc(sizeof(int16_t) * MAXVALUE);

gettimeofday(&t1, NULL);
 useLookUp(soundSample, lookUpTable);
 gettimeofday(&t2, NULL);

timeElapsedMSec = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
 printf("Lookup Table Approach\n");
 printf("timeElapsedMSec: %f\n", timeElapsedMSec);

return 0;
}

Results and Analysis

(time displayed in seconds)
AARCH64 X86_64
OPTIMIZATION FLAG NAIVE LOOK UP TABLE NAIVE LOOK UP TABLE
O0 8.82 4.019 2.198 2.391
O1 1.683 0.831 0.79 0.482
O2 1.867 0.822 0.814 0.482
O3 1.867 0.822 0.999 0.481

The results indicate that on both the AARCH64 and the X86_64 architectures, using compiler optimizations greatly decreased execution time on both approaches. Although based on my results, it would seem that this optimization was best on the O1 level as the times slightly increased with increasing optimization after that point. Furthermore, the optimization was much more pronounced in the AARCH64 architecture than the X86_64.

In our case, the distribution of the data did not actually matter since we used pseudo random values. Both approaches would be viable as even with our slowest approach of 62500000 samples/second could keep up with the standard 44100 samples per second x 2 channels. Additionally, the Lookup Table approach took more memory as the table would need to be generated before looking through it for the result. In order to further improve the lookup table, a better search algorithm like a binary search could be used to increase time efficiency.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s