[[Category:SPO600 Labs]]{{Admon/lab|Purpose of this Lab|In this lab, you will investigate the impact of different algorithms which produce the same effect. You will test and select one of two three algorithms for adjusting the volume of PCM audio samples based on benchmarking of two possible approaches.}}
[[Category:SPO600 Labs]]== Lab 3 6 ==
1. Write two different approaches to adjusting the volume of a sequence of sound samples:=== Background ===* The first one should scale a Digital sound is typically represented, uncompressed, as signed 16-bit integer by multiplying it by a volume scaling factor expressed as a floating point number in signal samples. There is are two streams of samples, one each for the range left and right stereo channels, at typical sample rates of 0-44.1or 48 thousand samples per second per channel, for a total of 88. This should be implemented as a function that accepts the sample 2 or 96 thousand samples per second (int16kHz) and scaling factor . Since there are 16 bits (float2 bytes) and returns per sample, the scaled sample data rate is 88.2 * 1000 * 2 = 176,400 bytes/second (int16~172 KiB/sec) or 96 * 1000 * 2 = 192,000 bytes/second (~187.5 KiB/sec).* The second one should do To change the same thingvolume of sound, using a lookup table each sample can be scaled (multiplied) by a pre-computed array volume factor, in the range of all 65536 possible values0.00 (silence)to 1. The lookup table should be initialized every time a different 00 (full volume factor is used). This should be implemented as * On a drop-in replacement for mobile device, the function above (same parameters and return value)amount of processing required to scale sound will affect battery life.
2. Test which approach is faster. Control the variables and use a large run of data (at least millions of samples). Use both [[SPO600 Servers|Xerxes and Aarchie]] for testing.=== Three Approaches ===
3Three approaches to this problem are provided: # The basic or Naive algorithm (<code>vol1.c</code>). This approach multiplies each sound sample by 0.75, casting from signed 16-bit integer to floating point and back again. Casting between integer and floating point can be [[Expensive|expensive]] operations.# A lookup-based algorithm (<code>vol2.c</code>). This approach uses a pre-calculated table of all 65536 possible results, and looks up each sample in that table instead of multiplying.# A fixed-point algorithm (<code>vol3.c</code>). This approach uses fixed-point math and bit shifting to perform the multiplication without using floating-point math. === Don't Compare Across Machines === In this lab, ''do not'' compare the relative performance across different machines, because the systems provided have a wide range of processor implementations, from server-class to mobile-class. However, ''do'' compare the relative performance of the various algorithms on the ''same'' machine. === Benchmarking === Get the files for this lab from one of the [[SPO600 Servers]] -- but you can perform the lab wherever you want (feel free to use your laptop or home system). Test on both an x86_64 and an AArch64 system. Review the contents of this archive:* <code>vol.h</code> controls the number of samples to be processed* <code>vol1.c</code>, <code>vol2.c</code>, and <code>vol3.c</code> implement the various algorithms* The <code>Makefile</code> can be used to build the programs Perform these steps:# Unpack the archive <code>/public/spo600-algorithm-selection-lab.tgz</code># Study each of the source code files and make sure that you understand what the code is doing.# '''Make a prediction''' of the relative performance of each scaling algorithm.# Build and test each of the programs.#* Do all of the algorithms produce the same output?#** How can you verify this?#** If there is a difference, is it significant enough to matter?#* Change the number of samples so that each program takes a reasonable amount of time to execute (suggested minimum 20 seconds, 1 minute or more is better).# Test the performance of each program.#* Find a way to measure performance ''without'' the time taken to perform the test setup pre-processing (generating the samples) and post-processing (summing the results) so that you can measure ''only'' the time taken to scale the samples. '''This is the hard part!'''#* How much time is spent scaling the sound samples?#* Do multiple runs take the same time? How much variation do you observe? What is the likely cause of this variation?#* Is there any difference in the results produced by the various algorithms?#* Does the difference between the algorithms vary depending on the architecture and implementation on which you test?#* What is the relative memory usage of each program?# Was your prediction accurate? === Deliverables === Blog about your experiments with a detailed analysis of your results, including memory usage, performance, accuracy, and trade-offs. Important Make sure you convincingly prove your results to your reader! -- Also be sure to explain what you're doing so that a reader coming across your blog post understands the context (in other words, don't just jump into a discussion of optimization results -- give your post some context). '''Optional - Recommended:''' Compare results across several '''implementations''' of AArch64 and x86_64 systems. Note that on different CPU implementations, the relative performance of different algorithms will vary; for example, table lookup may outperform other algorithms on a system with a fast memory system (cache), but not on a system with a slower memory system.* For AArch64, you could compare the performance on AArchie against the various class servers, or between the class servers and a Raspberry Pi 3 (in 64-bit mode) or an ARM Chromebook.* For x86_64, you could compare the performance of different processors, such as xerxes, your own laptop or desktop, and Seneca systems such as Matrix or lab desktops.
=== Things to consider ===
==== Design of Your Tests ====* Does the distribution Most solutions for a problem of this type involve generating a large amount of data matter?* If samples are fed at CD rate (44100 samples per second x 2 channels)in an array, processing that array using the function being evaluated, and then storing that data back into an array. The test setup can both algorithms keep up?* What is take more time than the actual test! Make sure that you measure the time taken in the code under test only -- you need to be able to remove the memory footprint rest of each approach?the processing time from your evaluation.* What is You may need to run a very large amount of sample data through the function to be able to detect its performance of each approach?.* What is If you do not use the output from your calculation (e.g., do something with the output array), the energy consumption of each approach?* Xerxes compiler may recognize that, and Aarchie have different performance profiles, so itremove the code you's not reasonable re trying to test. Be sure to compare performance between process the results in some way so that the optimizer preserves the machines, but it code you want to test. It is reasonable a good idea to compare the relative performance calculate some sort of verification value to ensure that both approaches generate the two algorithms in each contextsame results. Do you get similar results?* What Be aware of what other optimizations can be applied to this problem?tasks the system is handling during your test run, including software running on behalf of other users.
=== Competition Tips ===* For discussion {{Admon/tip|Analysis|Do a thorough analysis of the results. Be certain (and prove!) that your performance measurement ''does not'' include the generation or summarization of the test data. Do multiple runs and discard the outliers. Decide whether to use mean, minimum, or maximum time values from the multiple runs, and explain why you made that decision. Control your variables well. Show relative performance as percentage change, e.g., "this approach was NN% faster than that approach".}} {{Admon/tip|Non-Decimal Notation|In this lab, the number prefix 0x indicates a hexadecimal number, and 0b indicates a binary number, in harmony with the C language.}} {{Admon/tip|Time and Memory Usage of a Program|You can get basic timing information for a program by running <code>time ''programName''</code> -- the output will show the total time taken (real), the amount of CPU time used to run the application (user), and the amount of CPU time used by the operating system on behalf of the application (system). The version of the <code>time</code> command located in <code>/bin/time</code> gives slightly different information than the version built in classto bash -- including maximum resident memory usage: How fast can you scale 100 million int16 PCM sound samples?<code>/bin/time ''./programName''</code>}}
=== Tips ===
{{Admon/tip|SOX|If you want to try this with actual sound samples, you can convert a sound file of your choice to raw 16-bit signed integer PCM data using the [http://sox.sourceforge.net/ sox] utility present on most Linux systems and available for a wide range of platforms.}}
{{Admon/tip|Stack Limitstdint.h|Statically-allocated arrays will be placed in the stack space. The size of the stack space is controlled by per-process limits, inherited from the shell, and adjustable with the <code>ulimitstdint.h</code> command. Allocating an array larger than the stack header provides definitions for many specialized integer size limit will cause a segmentation fault, usually on the first writetypes. To see the current stack limit, use Use <code>ulimit -sint16_t</code> (displayed value is in KB; default is usually 8192 KB or 8 MB). To set the current stack limit, place a new size in KB or the keyword <code>unlimited</code>after the <code>for 16-s</code> argument.<br /><br />Alternate (and preferred) approach: allocate the array space with <code>malloc()</code> or <code>calloc()</code>bit signed integers.}}
{{Admon/tip|stdint.hScripting|The <code>stdint.h</code> header provides definitions for many specialized integer size types. Use <code>int16_t</code> for 16-bit signed integers.bash scripting capabilities to reduce tedious manual steps!}}
