Description
https://github.com/prof-rice/cse1325-prof
4 attachmentsSlide 1 of 4attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4
Unformatted Attachment Preview
Hashing Out Threads
Due Thursday, April 29 at 8 a.m.
CSE 1325 – Spring 2022 – Homework #12 – 1
Assignment Overview
Cryptocurrency such as Bitcoin is “mined” by creating a new struct containing some requested financial
transactions along with a check value that can be anything the miner wants. For others on the Internet to
accept the new struct into the shared list of valid structs, however, the hash value of that struct must be less
than a certain target value. The first machine to find a struct with a hash value less than the target “wins”, their
struct is added to the shared list, and they get some Bitcoin as a reward.
Let’s specify a very simple struct (OK, a class we’ll call WordWrapper), and then search for the smallest
hashCode among a long list of instances of this struct. What we’re really interested in here is to speed up
finding that smallest value (mining is a race, you see) by using more than one core to do the work. (This is a
very simplified version of the type of work Bitcoin miners do. You won’t become a Bitcoin Billionaire from this
homework, sadly!)
Full Credit
Baseline Code
Copy cse1325-prof/P12/baseline to your cse1325/P12/full_credit. In addition to the build.xml you know and
love, we also have a file called FindMinHash.java and its supporting word list all-words.txt, along with a
results.txt file into which you’ll record your results.
Class FindMinHash includes a nested class named WordWrapper – our “struct” whose instances’ minimal
hashCodes we seek. Its constructor accepts two indices into the word list. It concatenates the words into field
word and uses the indices to calculate field value. Naturally, method hashCode is also overridden, since that’s
the value of interest.
Class FindMinHash also has the following members:
• A constructor that loads all the words from all-words.txt into field wordList.
• A search method that accepts a starting index into the possible WordWrapper instances, as well as the
number of consecutive instances to search. When called, it will print out its parameters to help you along
with some thread information you’ll find useful later. The long index is split into 2 int indices which are
passed to WordWrapper’s constructor; if the resulting instance has a hashCode smaller than the smallest
yet seen, it is passed to method setBestWord.
• Method setBestWord verifies that its parameter has a smaller hashCode than the one in field bestWord.
If so, it updates bestWord and then returns bestWord.hashCode – the new value to beat.
• Method main parses the program arguments to find the number of hashes you want to check (and
optionally a different file of words), instances FindMinHash into findMinHash, then calls search to store
the WordWrapper object in your specified range with the smallest hashCode into bestWord, which it
prints.
Calibration
Since all machines calculate at different rates, you need to determine the number of hashes that takes your
machine between 30 and 45 seconds to search. Start with this command:
time java FindMinHash 1000
It will respond very quickly:
ricegf@antares$ time java FindMinHash 1000
Best word “A A” has hashCode 1,970,160
real
user
sys
0m0.070s
0m0.121s
0m0.020s
Now begin adding a 0 to the command until the “real” time is between 30 and 45 seconds. You may need to
fine tune once you’re close with intermediate numbers. Antares searches 750,000,000 hashes in about 35
seconds.
Record your parameter under QUESTION 1 in the results.txt file.
Add Threading
Now, modify FindMinHash to use multiple threads to search for small hashCode values.
Add a Program Argument for Number of Threads
I made this my second argument (with a default value of 1), and bumped the filename out to the third
parameter. This is coding you’ve done before, so don’t overthink it. I stored the number of threads requested in
final int numThreads.
Split the Search Among numThreads Threads
You’ll replace this line with quite a few additional lines.
findMinHash.search(0, maxHashes);
So if you had 1000 hashes to search with 10 threads, the first thread would search 0 to 99, the second thread
100 to 199, and so on until your last thread searched 900 to 999. You need to generalize these calculations for
whatever value is in numThreads.
You’ll need a Thread[numThreads] array to store your threads. Then you can launch each thread using a
lambda if you like, since the Runnable interface has a single required method – something like this.
new Thread(() -> findMinHash.search(start, step))
But it’s also fine if you want FindMinHash to implement the Runnable interface, and add your thread code as
new @Override method run().
Join the Threads
Once all the threads are running, iterate over your threads array to join them back to the main thread. Once
joined, the rest of the main function is unchanged.
Protect Field bestWord
Method setBestWord will be updating field bestWord for every thread. Sound like a thread contention issue?
You bet it is! Fix it using one of the approaches we discussed in Lecture 24.
I helped you out by making field wordList final, so you needn’t worry about thread contention with your threads
concurrent access to it.
Complete Full Credit Section of results.txt
The results.txt file has 3 more questions for the full credit section.
• QUESTION 2: Time your multi-thread version of FindMinHash with 1 through 16 threads. results.txt gives
you a single bash command you can use to do this (command lines save so much time!). Record the
time and program output.
• QUESTIONS 3 and 4: Answer the question here. We’ll only grade whether you responded, although
when reviewing the suggested solution we’ll discuss conventional wisdom.
Do an ant clean, then add, commit, and push ALL of the files in your cse1325/P12/full_credit directory.
You’re done!
Bonus
Calculating the range for each thread is a great deal of work, isn’t it? There must be a better way!
That way is called a work pool. Imagine a pool manager method that manages packets of work – say, 100
hashes to calculate per packet. When a thread needs work, it calls the pool manager and receives another
100 hashes to calculate. This keeps all threads equally busy, and absolves you of the task of micromanagine
which thread covers which hash.
Once all of the packets have been worked, the pool manager begins returning empty packets which signals
the threads all work is complete, so the thread exits. Once all threads have exited and rejoined the main
thread, the result is printed and the program exits.
Work pools have the delightful characteristic of being self-balancing – each thread does its work as fast as it
can, and all threads are kept busy. This is particularly nice on assymetric laptops, where some cores are
optimized for performance and others for low power. All cores can contribute to completing the work to the
extent they are able.
Creating the Work Pool
Add a method named nextPacket() which returns the first int in a 100 sequential indices for which hashes are
required. Protect nextPacket() from thread interference. Once all indices have been assign, begin returning -1
to signal that threads should now exit.
Rewrite your run() method or lambda to loop, requesting a new packet and then calculating those 100 hashes.
When nextPacket() returns -1, exit the thread.
Complete the questions in results.txt. Then do an ant clean and add, commit, and push ALL of the files in
your cse1325/P12/bonus directory. You’re done!
CSE 1325: Object-Oriented Programming
Lecture 24
A Very Simple Introduction to
Concurrency
Mr. George F. Rice
george.rice@uta.edu
ERB 402
Office Hours:
Tuesday Thursday 11 – 12
Or by appointment
A biologist, a chemist, and a statistician are hunting when a deer wanders by.
The biologist misses 5 feet to the left and the chemist 5 feet to the right.
The statistician yells “We got ’em!”
This work is licensed under a Creative Commons Attribution 4.0 International License.
Overview: Concurrency
●
●
●
Brief history
Uses / Advantages
Java Support
Runnable Interface
– Thread class
– Thread.sleep
– Thread Interference
– Synchronized / Mutex
Examples
– Matrix multiplication
– Horse racing simulation
–
●
Modern Jockey by deavvi per the Pixabay License
https://pixabay.com/illustrations/jockey-horse-with-jockey-horse-5503104/
A Brief History of Concurrency
●
Moore’s Law (paraphrased): Computer tech (originally
transistor density) doubles every 2 years
–
●
By the 21st century, Moore’s Law began to crack
–
–
●
Processor speeds topped out around 4 GHz (2.8 – 3.4 common)**
Transistor density continued for some time – but how to best use?
Multi-Core Processor – a chip with multiple cores, or
ALU*/register sets, each running a separate thread
–
●
CPU speed, transistor and memory density, disk capacity, etc.
Intel worked out use of one ALU with 2 register sets, interleaving 2
threads of execution – Hyperthreading
Deployed 24 hyperthreaded core machines in 2014 – but how
to utilize so many cores?
Concurrency
* Arithmetic / Logic Unit
** Overlocking is a thing, though – https://valid.x86.fr/records.html
Concurrency
●
●
●
Concurrency – Performing 2 or more algorithms
(as it were) simultaneously
Process – A self-contained execution
environment including its own memory space.
Thread – An independent path of execution
within a process, running concurrently
(as it appears) with others within
a shared memory space.
Process
Process
Thread
Thread
Thread
Thread
Thread
Thread
Operating System
Conceptual Model
Good Uses for Concurrency
●
●
●
●
●
Perform background processing independent of the user
interface, e.g., communicating the game state to apps
Programming logically independent program units, e.g., the
behavior of each non-player character in a game
Processing small, independent units of a large problem, e.g.,
calculating the shaded hue of each pixel in a rendered
photograph – or rendering an entire movie frame by frame!
Periodic updating of a display or hardware unit, e.g., updating the
second hand of a clock
Periodic collection of data, e.g., capturing wind speed from an
anemometer every 15 seconds
Advantages of Threads
●
Better utilization of multi-core / multi-processor
machines
–
●
On our 24-core machines, Parallel Implementation of
gzip (pigz) was more than 10x faster than standard
gzip – cut 3 hour compression to 15 min
Better mapping of problem to code
–
For Chinese Checkers with 5 AI players and 1 human
player, each player as a thread sharing a common
board object is a more natural implementation
–
Better still, AI implementation can analyze board while
other players are “thinking” – see first bullet
Advantages of Threads
(For C++ Programmers)
●
Faster C++ builds!*
Time measures how long
the make command runs
– real is what you experience
– user is total of all cores
– sys is time in system overhead
-j 4 means “use 4 threads”
A 60% reduction in build time
(1.5 vs 3.7 seconds) for 3 chars!
* Wouldn’t this have been helpful sooner? Javac isn’t concurrent, regrettably.
Creating a Simple Java Thread
●
Class Thread represents a thread of execution
–
Implementing interface Runnable makes it thread-compatible
–
Each Thread object has a unique thread ID (.getId())
–
Each started thread can be “joined” back to the main thread
(an unstarted thread can’t)
public class SimpleThread implements Runnable {
// Interface Runnable requires overriding the run method.
@Override
public void run() {
for(int i=0; i 0) numMultiplies = Integer.parseInt(args[0]);
if(args.length > 1) numThreads = Integer.parseInt(args[1]);
}
}
if(numThreads == 1) {
For 1 thread, we just calculate the
MatrixMultiply mm = new MatrixMultiply();
for(int i=0; i
Purchase answer to see full
attachment
Tags:
programming
cryptocurrency
Billionaire
User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.
