CS 218 Assignment #12 solution

Description

Purpose: Become more familiar with operating system interaction, threading, and race conditions.
Points: 100 50 for program and 50 for write-up
Scoring will include functionality, documentation, and coding style
Assignment:
In recreational number theory, a Narcissistic
number1
is a number that is the sum of its own
digits each raised to the power of the number of
digits. For example, given 8202 which has 4
digits, the sum of each number raised to 4 is
8208.
8208 = 8
4
+ 2
4
+ 0
4
+ 8
4
Write an assembly language program provide a
count of the Narcissistic numbers between 0 and
some limit. For example, between 1 and 10,000
there are exactly 17 Narcissistic numbers (0, 1,
2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634,
8208, 9474).
In order to improve performance, the program
should use threads to perform computations in
parallel. The program should read the thread
count and number limit in septenary from the
command line in the following format;
“./narCounter -t <-1|2|3|4|5|6> -lm
”. For example:
./narCounter -t 4 -l 564355
The following routines should be created:
• A value returning function, getUserArgs(), that reads and verifies the command line arguments.
This includes error and range checking based on provided parameters (in the template). The
error strings are predefined in the template. The function should call the aSept2int() function.
• Value returning function aSept2int() to convert an ASCII/septenary string to integer. If the
passed string is a valid ASCII/septenary value the value should be returned (via reference) and
the function should return true. If there is an error, the function should return false. Note, the
integer being returned is a quad (64-bits) which is different from previous assignments.
• A void function, narcissisticNumberCounter(), that will be called as a thread function and
determine the count of narcissistic numbers. The thread must perform updates to the global
variables in a critical section to avoid race conditions. See below sections for additional detail.
1 For more information, refer to: https://en.wikipedia.org/wiki/Narcissistic_number
The Simpsons, Season 17 Episode 22
The first, 8,191 is a Mersenne prime, a prime number
that can be divided only by itself and one. And, 8,128,
is a perfect number, where the sum of proper divisors
add up to it. Then, 8,208 is a narcissistic number,
which has four digits and, if you multiply each one by
itself four times, the result adds up to 8,208.
Thread Function:
Create a thread function, narcissisticNumberCounter() that performs the following operations:
• Print the thread starting message (predefined).
• Each thread will obtain the next bock of numbers to check (via global variable, currentIndex)
and increment the global by BLOCK_SIZE (range of numbers to check) using the predefined
constant.
◦ Loop while the next number is £ limitValue (globally available) to check each number in
the block.
◦ If a number is narcissistic, atomically increment narcissisticCount variable.
◦ When the range of numbers has been processed, a new block should be obtained.
◦ If the limit value is exceeded the function should exit.
When obtaining the next block to check and incrementing the global currentIndex variable, these
operations must be performed as a critical section2
(i.e., locked and unlocked using the provided
spinLock() and spinUnlock() functions). As the numbers are being checked, no locks are needed.
Once a number has been determined to be narcissistic, the number should be placed in the
narcissisticNumbers[] array and the narcissistic counter should incremented accordingly. These
operations must also be performed as a critical section.
It is recommended to complete and test the program initially with only the single sequential thread
before testing the parallel threads. In order to debug, you may wish to temporarily insert a direct call
(non-threaded) to the narcissisticNumberCounter() function.
Results Write-Up
When the program is working, complete additional timing and testing actions as follows;
● Use the provided script file to execute and time the working program.
● Compute the speed-up3
factor from the base sequential execution and the parallel execution
times. Use the following formula to calculate the speed-up factor:
SpeedUp =
ExecTimesequential
ExecTime parallel
● Remove the locking calls (the spinLock() and spinUnlock() calls and the ‘lock’) and re-execute
the program using a limit of 50,000,000 (11446644117) for 1, 2, 3, and then 4 threads. A
provided timing script will help capture these results.
○ The Unix time command (as per asst #11B) should be used to obtain the execution times.
Use the “real” time.
● Create a final write-up including a copy of the program output from the timing script file and an
explanation of the results. The explanation must address:
○ the final results for 1, 2, 3, and 4 thread executions, including final results (list of
perfect/abundant/deficient numbers) and the execution times for both each.
○ the speed-up factor from 1 thread to 2, 3, and 4 threads (via the provided formula)
○ simple chart plotting the execution time (in seconds) vs thread count (see example below).
○ the difference with and without the locking calls for the parallel execution
■ explain specifically what caused the difference
2 For more information, refer to: https://en.wikipedia.org/wiki/Critical_section
3 For more information, refer to: https://en.wikipedia.org/wiki/Speedup
The explanation part of the write-up (not including the output and timing data) should be less
than ~300 words. Overly long explanations will be not be scored.
Below is an example of the type of chart to include
Such graphs are most easily done using a spreadsheet. An optional example spreadsheet is
provided for reference.
Assignment #12 Timing Script
In order to obtain the times for the write-up a timing script is provided. After you download the script
file, a12timer, set the execute permission as follows:
ed-vm$ chmod +x a12timer
ed-vm$ ./a12timer narCounter
The script file will expect the name of the executable as an argument (as shown).
The script may take a while to execute, but no interaction is required. The script will create an output
file, a12times.txt, which will be included in the submission and the data be used create the writeup.
1 2 3 4
0
100
200
300
400
500
600
CS 218 – Assignment #12
Execution Time vs Thread Count
Threads
Times (seconds)
Submission:
• All source files must assemble and execute on Ubuntu and assemble with yasm.
• Submission three (3) files
◦ Submit Source File
▪ Note, only the functions file (a12procs.asm) will be submitted.
◦ Submit Timing Script Output
▪ Submit the a12times.txt file (created after executing the a12timer script).
◦ Submit Write Up file (write_up.pdf)
▪ Includes system description, speed-up amounts, and results explanation (per above).
• Once you submit, the system will score the code part of the project.
◦ If the code does not work, you can (and should) correct and resubmit.
◦ You can re-submit an unlimited number of times before the due date/time (at a maximum
rate of 5 submissions per hour).
• Late submissions will be accepted for a period of 24 hours after the due date/time for any given
assignment. Late submissions will be subject to a ~2% reduction in points per an hour late. If
you submit 1 minute – 1 hour late -2%, 1-2 hours late -4%, … , 23-24 hours late -50%. This
means after 24 hours late submissions will receive an automatic 0.
Program Header Block
All source files must include your name, section number, assignment, NSHE number, and program
description. The required format is as follows:
; Name:
; NSHE ID:
; Section: