Get a Free Quote

Solved–Assignment #6 –Solution

$30.00 $19.00

Assignment: Part A: In recreationa number theory, palindromic number1 is a number that remains the same when its digits are reversed. For example, 16461 is a palindromic number since when it is reversed is the same. Write a threaded C++11 program to find the count palindromic numbers between 1 and a user provided limit (inclusive)…

You’ll get a: . zip file solution

 

 
Categorys:

Description

5/5 – (2 votes)

Assignment:

Part A:

In recreationa number theory,

  • palindromic number1 is a number that remains the same when its digits are reversed. For

example, 16461 is a palindromic number since when it is reversed is the same.

Write a threaded C++11 program to find the count palindromic numbers between 1 and a user provided limit (inclusive) and determine the percentage. For example, between 1 and 1,000,000 there are exactly 1988 palindromic numbers (0.001998%).

In order to improve performance, the program should use threads to perform computations in parallel. The program should read the thread count and limit from the command line in the following format:

./palNums -t <threadCount> -l <limitValue>

The command line argument processing must be in a dedicated function. The thread count should be between MIN_THREAD_COUNT and MAX_THREAD_COUNT (inclusive) and the limit value should be between MIN_LIMIT and MAX_LIMIT (inclusive). As such, you will need to use unsigned long long as the data type. You will need to create your own main source file and makefile. Refer to the example execution for output formatting. Global variables will be required for the counts array and limit value. Define the following constants:

static

const unsigned long long

static

const unsigned long long

static

const unsigned long long

static

const unsigned

long

long

static

const unsigned

long

long

MIN_THREAD_COUNT = 1;

MAX_THREAD_COUNT = 64;

MIN_LIMIT = 10;

MAX_LIMIT = 100000000000;

PAL_STEP = 10000;

Additionally, the program should use the C++11 high resolution clock to provide an execution time in milliseconds. Refer to the following pages for a detailed explanation of how to use the C++ high resolution clock.

Each thread should check PAL_STEP number of values for palindromic numbers. Each thread should place its count into a palCounts[] array based on its thread number which is set and passed from the main. The main will need to add the palCounts[] to determine the final result.

1 For more information, refer to: https://en.wikipedia.org/wiki/Palindromic_number

Part B:

When completed, use the provided timing script, ast6Exec, to execute the program various

times with single and multiple threads (>30 minutes). The script writes the results to a file (a6times.txt). To ensure consistent results, use the cssmp.cs.unlv.edu which has 32 cores (uses CS login). Enter the thread counts and times into a spreadsheet and create a line chart plot of the execution times versus the thread counts. Refer to the example below for how the plot should look.

Note, the default g++ compiler version on CSSMP does not support the C++11 standards. In order to use the current C++11 standard, you will need to type the following (once per session):

scl enable devtoolset-2 bash

Create and submit a brief write-up (PDF format), not to exceed ~500 words, including the following:

•

•

•

•

•

•

Name, Assignment, Section.

Palindromic Numbers

Include a copy of the timing

Thread Count vs Execution Times

script output

(ms)

Include a copy of the chart (see

500000

Time

simplified example to right).

Summarize the results from the

Execution

0

timing script.

1

2

4

8

16

32

Determine the percentage

Thread Count

speed-up2 using the below

formula (for each thread count

> 2):

speedUp = Timesingle

Timenew

Remove the mutex locks and execute the program. Report the results. Include a description of what happened and an explanation of why.

Submission:

When complete, submit:

●

●

Part A → A copy of the source files via the class web page (assignment submission link) by class time on the due date. The source files, with an appropriate makefile, should be placed in a ZIP folder. The grader will download, uncompress, and type make (so you must have a valid, working makefile).

Part B → A copy of the write-up including the chart (see example). Must use PDF format.

Assignments received after the due date/time will not be accepted. Make sure your program includes the appropriate documentation. See Program Evaluation Criteria for CS 302. Note, points will be deducted for especially poor style or inefficient coding.

2 For more information, refer to: https://en.wikipedia.org/wiki/Speedup

Threads

C++11 introduced a new thread library. This library includes utilities for starting and managing threads. It also contains utilities for synchronization like mutexes and other locks, atomic variables and other concurrency related functions.

When you create an instance of a std::thread, it will automatically be started. When you create a thread you have to give it the code by passing the function as a pointer. For example, the following is a very common (but not useful) threaded Hello World program:

#include <iostream>

#include <thread>

using namespace std;

void helloThdFunc(int a1)

{

cout << “Hello from thread: ” << a1 << endl;

}

int main(){

thread thd1(helloThdFunc, arg1); // start thread, pass arg

thd1.join(); // wait for thread to finish

}

return 0;

As shown, the join() is used to wait for the thread to complete. You must wait for all threads to complete before terminating the program. You can dynamically create an array of threads in order to effectively handle a varying number of threads.

In addition, mutex’s must be used to avoid race data races. To use a mutex, first declare a mutex variable (global in this example) and use the mutex variable as shown in order to avoid race conditions.

mutex myMutex;

void someThreadFunc(){

lock_guard<mutex> guard(myMutex);

// perform applicable stuff here…

}

The lock_guard<mutex> guard(mutexVariable) operation will ensure that the

subsequent statements are locked and thus only executed by one thread at a time. Specifically, if the mutex is free, it will be locked and the the subsequent code will executed. If the mutex is already locked, all other threads will be blocked from executing the code until one obtains the lock. The lock will be released when it goes out of scope (in this example, at the end of the function).

To compile the, include the -std=c++11 option to get the C++11 support activated. Additionally include the -pthread option for the threading libraries. You will need to #include <thread> and #include <mutex> as part of the program includes.

C++11 High Resolution Timer

The functions for the C++11 high resolution timer are located in the chrono library.

// get start timer…

auto t1 = chrono::high_resolution_clock::now();

// do stuff…

// get end time…

auto t2 = chrono::high_resolution_clock::now();

  • show results with times cout << “Program took: ” <<

    • std::chrono::duration_cast<std::chrono::milliseconds> (t2 – t1).count() << ” milliseconds” << endl;

You will need to #include <chrono> as part of the program includes.

Hardware Core Count

The hardware count can be obtained as follows:

unsigned long hwthd = thread::hardware_concurrency();

Example Execution

Below are some example executions for reference.

ed-vm% ./palNums -t 8 -l 1000000

—————————————————————–

CS 302 – Assignment #6

Hardware Cores: 4

Thread Count: 8

Numbers Limit: 1000000

Results:

Count of palindromic numbers between 1 and 1000000 is 1998 Percentage of palindromic numbers: 0.001998%

Threads took: 6 milliseconds

ed-vm%

ed-vm%

ed-vm% ./palNums

Usage: ./palNums -t <thereadCount> -l <limit> ed-vm%

ed-vm% ./palNums -t 80 -l 1000000

Error, invalid thread count.

ed-vm%

ed-vm% ./palNums -t 8 -l 3

Error, invalid number limit (3).

ed-vm%

ed-vm%

ed-vm%

ed-vm% ./palNums -t 1 -l 100000000

—————————————————————–

CS 302 – Assignment #6

Hardware Cores: 4

Thread Count: 1

Numbers Limit: 100000000

Results:

Count of palindromic numbers between 1 and 100000000 is 19998 Percentage of palindromic numbers: 0.00019998%

Threads took: 2864 milliseconds

ed-vm%

ed-vm%

ed-vm% ./palNums -t 4 -l 100000000

—————————————————————–

CS 302 – Assignment #6

Hardware Cores: 4

Thread Count: 4

Numbers Limit: 100000000

Results:

Count of palindromic numbers between 1 and 100000000 is 19998 Percentage of palindromic numbers: 0.00019998%

Threads took: 821 milliseconds

ed-vm%

ed-vm%

ed-vm% ./palNums -t 4 -l 10000000000

—————————————————————–

CS 302 – Assignment #6

Hardware Cores: 4

Thread Count: 4

Numbers Limit: 10000000000

Results:

Count of palindromic numbers between 1 and 10000000000 is 199998

Percentage of palindromic numbers: 1.99998e-05%

Threads took: 97424 milliseconds

ed-vm%

ed-vm%

  • Homework 3: Mbed Setup Solution

    Homework 3: Mbed Setup Solution

    $35.00 $24.00
    Buy Answer
  • Homework 2: When Harry Met Sally Solution

    Homework 2: When Harry Met Sally Solution

    $35.00 $24.00
    Buy Answer
  • Project 3 Complex Number Calculator Solution

    Project 3 Complex Number Calculator Solution

    $35.00 $24.00
    Buy Answer
  • Homework 4: A* Pathfinding Solution

    Homework 4: A* Pathfinding Solution

    $35.00 $24.00
    Buy Answer
  • Project 1A: Transformation Matrices Solution

    Project 1A: Transformation Matrices Solution

    $35.00 $24.00
    Buy Answer