Analysis of sorting algorithms in BeagleBone Black

This project aims to analyze the execution performance of three sorting algorithms are BubbleSort, QuickSort and MergeSort. With comparative information using graphs on running the algorithms on BeagleBone Black and on another computer.

Menu

1. The BeagleBone Black

• Warnings

2. Connecting to BeagleBone
3. Requirements for doing the analysis
4. Gnuplot Tutorial

• Install gnuplot
• Generating the statistical graph

5. Running on the Computer
6. Running on BeagleBone Black

• Before (Computer)
• Running (BeagleBone Black)
• After (Computer)

7. Results

• Computer 1 (Pentium Dual Core Processor)
• Computer 2 (i7 Octa Core Processor)
• BeagleBone Black (Single Core)

8. Conclusion
9. Members
10. References

1. The BeagleBone Black

BeagleBoard (or simply Beagle) is a single board computer developed by Texas Instruments. The Beagle is classified as free hardware under the Creative Commons SharedAlike license.

The BeagleBone Black (BBB) is one of the BeagleBoard versions, this version has 512 Mb of RAM, a Cortex-A8 processor with a clock of 1GHz and 4GB of flash memory, and still comes with Debian GNU installed at the factory.

i. Warnings

1. Do not place the BeagleBone on metal surfaces;
2. Turn on the Beagle Bone: hold down the "user" button until the LEDs start blinking, connect the USB cable, and wait for the LEDs to flash.
3. Switch off with the appropriate command (sudo shutdown -h now) or use the buttons. NEVER PULL THE POWER CORD OR USB POWER;
4. GPIO are 3.3v tolerant;
5. Input: 4mA - 6mA
6. Output: 8mA
7. ADC are 1.8v tolerant;
8. Do not modify the system root password (eMMC);
9. Disconnect all wires from the card when making a change in the electronics.

2. Connecting to BeagleBone

To connect to the BeagleBone Black you need to connect the USB cable to the computer and then send the shh command as follows:

shh [email protected]

So you need to log in to BeagleBone Black. The password is: temppwd

Now you can access BeagleBone.

3. Requirements for doing the analysis

• Use a computer with some Linux distribution (We indicate Ubuntu).
• Install the following packages to update C ++.

sudo apt-get install gcc-5-multilib g++-5-multilib

• Download and install the Texas Instruments SDK and install using the following commands and advance all options by clicking "Next".

chmod +x nomedoarquivobaixado
./nomedoarquivobaixado

5. Gnuplot Tutorial

Gnuplot is a software that prevents the creation of graphics (2D and 3D) for various environments (UNIX, Windows, Macintosh, etc.). Here are some basic commands for using this tool.

i. Install gnuplot

sudo apt-get install gnuplot-x11

ii. Generating the statistical graph

1. Access the directory containing the "clock.dat" and "time.dat" files (which were generated by the execution of the methods) and "grafico.gnu" (gnuplot execution script) by the terminal:

cd data

2. Type the command in Terminal:

gnuplot grafico.gnu

To create the graphics just run the gnuplot using the gnuplot script of this project.

gnuplot performance.gnuplot

5. Running on the Computer

At the root of the project enter the directory "dist-64bits" or "dist-32bits" Depending on your operating system and run the program:

cd dist-64bits
./AnalysisTime

You can program and compile on your computer and send the executable to BeagleBone. To test this project, simply clone this project and execute the commands.

6. Running on BeagleBone Black

É possível programar e compilar no seu computador e enviar o executável para a BeagleBone. Para fazer os testes deste projeto basta clonar esse projeto e executar os comandos.

i. Before (Computer)

Enter the "AnalysisTime" source code folder and open the "compila.sh" file and see if the "source" directory is actually the "SDK Texas Instruments" address installed as specified in previous sections. Example:

source /opt/ti-processor-sdk-linux-am335x-evm-02.00.01.07/linux-devkit/environment-setup

Verify that the executable name is the same as the one specified in "AnalysisTime.pro" as follows:

sshpass -p 'temppwd' scp AnalysisTime [email protected]:~

Now go to BeagleBone by ssh (more information can be viewed in previous sections):

ssh [email protected]

ii. Running (BeagleBone Black)

Already connected to Beagle (it is preferable to have the gnuplot installed in the beagle to facilitate the process, this can be done in the gnuplot install section) run the program:

./AnalysisTime

After execution, a dados-coletados directory is created with files containing the information to be plotted on the chart. and if the gnuplot has already been installed before, you already have the images with graphics. Go back to your pc:

exit

iii. After (Computer)

At the root of the project run the script get-results-beagle-scp.sh, enter the password as requested, if no permission is provided with:

chmod +x get-results-beagle-scp.sh
./get-results-beagle-scp.sh

After that the data of the beagle can be analyzed in the directory Dados-beagle, if there are no images with the graphics, generate with:

gnuplot performance.gnuplot

7. Results

In this section we have the results of the tests of the algorithms BubbleSort, QuickSort and MergeSort.

i. Computer 1 (Pentium Dual Core Processor)

Settings:

• Intel Pentium 3GHz x2
• 2 Gb of RAM
• 64 bits
• Ubuntu

The program ran alone on the computer.

ii. Computer 2 (i7 Octa Core Processor)

Settings:

• Intel Core i7 2.40GHz x8
• 8 Gb of RAM
• 64 bits
• Ubuntu

The program was run in parallel with other programs (Spotify, Chrome, Atom, File Manager and PDF Viewer).

iii. BeagleBone Black (Single Core)

The program ran alone on the computer.

8. Conclusion

We conclude as soon as the hardware architecture greatly influences performance, we can see this by the graphs shown in the results of the analysis.

We noticed that there is a big difference in the graphs between the execution in the computers and the BeagleBone, but there are similarities in relation to the growth of the graphs, these correspond to the complexity of the algorithms.

After these tests how can we answer which function performs the best performance analysis of sorting algorithms?

As we can see, the Clock function allows a more detailed analysis of the data, since the small order that a clock unit represents, however, when we analyze the data with more precision, we can easily reach the representative limit of the numerical unit, and the consequence is the occurrence of Overflow causing an inconsistency in the final data. The Time function is very useful to represent large values, since its representative unit is in seconds, in that way it would analyze in a "magnificent" way the execution of algorithms with years of duration, although there is a growth limit as well the Clock function, the big problem of the Time function is in the performance analysis of algorithms in short time intervals, since it is not possible to measure large ones such as milliseconds or nanoseconds.

Therefore, the best answer to the above question depends on what will be analyzed: algorithms that last a nanosecond, or complex ordering algorithms run on vectors with more than 100,000 elements. The Clock function is most useful for accurate analysis, but not for large-time analysis, and the Time function is most useful in very complex and time-consuming algorithms, but it is much less accurate than the Clock function.

9. Members

• Breno Maurício de Freitas Viana
• Felipe Barbalho Rocha

9. References

• BubbleSort - Disponibilizado pelo professor Ivanovitch
• QuickSort
• MergerSort
• BeagleBoard
• Usando Gnuplot para gerar bons gráficos
• Gnuplot - Manual simplificado para iniciantes
• Professor Ivanovitch lesson slides