22. How does timing work in a computer?#
22.1. IDEA incentive#
If the course reaces 75% final response rate then, the free corrections will extend to final grading.
The last day to submit (or revise) any work is otherwise Tuesday May 7 Grading after that date maybe still include the “request changes” feedback but revisions will not be considered toward your grade.
22.2. Recall our model Computer#
We have talked about the ALU at length and we have touched on memory, but next we will start to focus on the Control unit.
We discussed that the operations we need to carry out is mostly
22.3. Control Unit#
The control unit converts binary instructions to signals and timing to direct the other components.
22.3.1. What signals?#
We will go to the ALU again since the control unit serves it to figure out what it needs.
Remember in the ALU, has input signals that determine which calculation it will execute based on the input.
22.3.2. Why Timing signals?#
Again, the ALU itself tells us why we need this, we saw that different calculations the ALU does take different amount of times to propagate through the circuit.
Even adding numbers of different numbers that require different number of carries can take different amount of times.
So the control unit waits an amount of time, that’s longer than the slowest calculation before sending the next instruction. It also has to wait that long before reading the output of the ALU and sending that result to memory as needed.
22.4. What is a clock?#
In a computer the clock refers to a clock signal, historically this was called a logic beat. This is represented by a sinusoidal (sine wave) or square (on, off, on, off) signal that operates with a constant frequency.
This has changed a lot over time.
The first mechanical analog computer, the Z1 operated at 1 Hz, or one cycle per second; its most direct successor moved up to 5-10Hz; later there were computers at 100kHz or 100,000Hz, but where one instruction took 20 cycles, so it had an effective rate at 5kHz.
Try it Yourself
Look up the CPU speed of your computer and your phone. How do they compare.
22.5. Execution Times#
cd spring2024/
time grep "index" _practice/*
_practice/2024-01-25.md:1. read Chapter 1, "Decoding your confusion while coding" in [The Programmer's Brain](https://www.manning.com/books/the-programmers-brain#toc) add a file called {index}`brain.md` to your kwl repo that summarizes your thoughts on the chapter. Do you think this information will help you approach learning more effectively? why or why not? How, if at all, does it changes how you think about debugging and learning to program? Give examples of how you have encountered the different types of confusion in your prior programming experiences. (to help you get good strategies and prime for things we will see in the next few weeks)
_practice/2024-01-25.md:2. Make a concept map of your current understanding of git and github {index}`git-basics-map.md`. Use [mermaid](https://mermaid-js.github.io/mermaid/#/) syntax, to draw your map. GitHub can render it for you including while you work using the preview button. (review what we have learned so far; think about connections + learn a new tool)
_practice/2024-01-30.md:3. Try using setting up git using your favorite IDE's git integration (not its terminal) or GitHub Desktop. Make a file {index}`gitgui.md` and include some notes of how it went. Give the file a heading like `# Setting up <tool name>` with the actual tool name you setup in the title (eg Github Desktop or VSCode source control panel or ...). Was it hard? easy? what did you figure out or get stuck on? Is the terminology consistent to the terminal or does it use different terms?
_practice/2024-01-30.md:4. Design a small demo to illustrate the difference between git add and git commit and how they impact `git push`. Write your demo in {index}`stage_commit.md`. Compare what happens based on what you can see on GitHub and what you can see with git status. Denote what you can tell about each case from the terminal and what you can tell from GitHub.com. For this demo, test things either using the files for this badge in your KWL repo or create a new sandbox repo where your account (not the course) is the owner.
_practice/2024-02-01.md:1. Create a merge conflict in your KWL repo on the branch for this issue and resolve it using your favorite IDE, then create one and resolve it on GitHub in browser (this requires the merge conflict to occur on a PR). Describe how you created it, show the files, and describe how your IDE helps or does not help in {index}`merge_conflict_comparison.md`. Give advice for when you think someone should resolve a merge conflict in GitHub vs using an IDE. (if you do not regulary use an, IDE, try VSCode) *You can put content in the file for this step for the purpose of making the merge conflicts for this exercise.*
_practice/2024-02-01.md:3. In {index}`branches-forks.md` in your KWL repo, compare and contrast branches and forks; be specific about their relationship. You may use mermaid diagrams if that helps you think through or communicate the ideas. If you use other resources, include them in your file as markdown links.
_practice/2024-02-06.md:2. Get set up so that you can pull from the course website repo and push to your own fork of the class website by cloning the main repo, then forking it and adding your fork as an additional [remote](https://docs.github.com/en/get-started/getting-started-with-git/managing-remote-repositories#adding-a-remote-repository). Append the commands used and the contents of your `spring2024/.git/config`to a {index}`terminalpractice.md` (hint: `history` outputs recent commands and redirects can work with any command, not only echo). Based on what you know so far about forks and branches, what advantage does this setup provide? (answer in the `terminal_practice.md`)
_practice/2024-02-06.md:4. Organize a folder on your computer ( good candidate may be desktop or downloads folder), using only a terminal to make new directories, move files, check what's inside them, etc. Answer reflection questions in a new file, {index}`terminal_organization_adv.md` in your kwl repo. Tip: Start with a file explorer open, but then try to close it, and use only command line tools to explore and make your choices. If you get stuck, look up additional commands to do acomplish your goals.
_practice/2024-02-08.md:1. Explore the [tools for conventional commits](https://www.conventionalcommits.org/en/about/#tooling-for-conventional-commits) and then pick one to try out. Use one of the tools that helps making conventional commits (eg in VSCode or a CLI for it)for a series of commits adding "features" and "bug fixes" telling the story of a code project in a file called {index}`commit-story.md`. For each edit, add short phrases like 'new feature 1', or 'next bug fix' to the single file each time, but use conventional commits for each commit. In total make at least 5 different types of changes (types per conventional commits standard) including 2 breaking changes and at least 10 total commits to the file.
_practice/2024-02-08.md:2. [learn about options for how git can display commit history](https://git-scm.com/book/en/v2/Git-Basics-Viewing-the-Commit-History). Try out a few different options. Choose two, write them both to a file, {index}`gitlog-compare.md`. Using a text editor, wrap each log with three backticks to make them "code blocks" and then add text to the file describing a use case where that format in particular would be helpful. **do this after the above so that your git log examples include your conventional commits**
_practice/2024-02-15.md:2. Learn about the documentation ecosystem in another language that you know using at least one official source and additional sources as you find helpful. In {index}`docs_ecosystems.md` include a summary of your findings and compare and contrast it to jupyter book/sphinx. Include a [bibtex based bibliography](https://jupyterbook.org/en/stable/content/citations.html) of the sources you used. You can use [this generator](https://url-to-bibtex.vercel.app/) for informal sources and [google scholar](https://digitalmeasures.oregonstate.edu/training/export-bibtex-google-scholar) for formal sources.
_practice/2024-02-20.md:1. Describe a type of project where it would be worth it for you to learn a language you have never used before in {index}`newlanguage.md` This should be based in what types of features for the language your project would require and/or what would contribute to the long term health of the project.
_practice/2024-02-20.md:2. Learn about one of the following languages that you have not used before: [R](https://www.r-project.org/), [Julia](https://julialang.org/), [Clojure](https://clojure.org/guides/getting_started), [Zig](https://ziglang.org/), [Go](https://go.dev/), [erlang](https://www.erlang.org/), [Elixir](https://elixir-lang.org/) or another language you are curious about that appeared in the Developer survey. For example you might be interest in the [top paying languages](https://survey.stackoverflow.co/2023/#technology-top-paying-technologies). Use the official documentation. Answer the following questions in {index}`languagelearning.md`:
_practice/2024-02-22.md:1. Most real projects partly adhere and at least partly deviate from any major design philosophy or paradigm. Add a `## Unix Philosophy` section to your {index}`software.md` about how that project adheres to and deviates from the unix philosophy. Be specific, using links to specific lines of code or specific sections in the documentation that support your claims. Provide at least one example of both adhering and deviating from the philosophy and three total examples (that is 2 examples for one side and one for the other). You can see what badge `software.md` was previously assigned in and the original instructions [on the KWL file list](https://compsys-progtools.github.io/spring2024/genindex.html).
_practice/2024-02-22.md:2. create {index}`methods.md` and answer the following:
_practice/2024-02-27.md:1. Read about different workflows in git and add responses to the below in a {index}`workflows.md` in your kwl repo. Two good places to read from are [Git Book](https://git-scm.com/book/en/v2/Distributed-Git-Distributed-Workflows#ch05-distributed-git) and the [atlassian Docs](https://www.atlassian.com/git/tutorials/comparing-workflows)
_practice/2024-02-27.md:3. Find the hash of the blob object that contains the content of your {index}`workflows.md` file and put that in the comment of your badge PR for this badge.
_practice/2024-02-29.md:1. Read more details about [git internals](https://git-scm.com/book/en/v2/Git-Internals-Git-Objects) to review what we did in class in greater detail. Make a file {index}`gitplumbingdetail.md` and create a visualization that is compatible with version control (eg can be viewed in plain text and compared line by line, such as table or mermaid graph) that shows the relationship between at least **three** porcelain commands and their corresponding plumbing commands (generally more than one each).
_practice/2024-02-29.md:2. Create {index}`gitislike.md` and explain main git operations we have seen (add, commit, push) in your own words in a way that will either help you remember or how you would explain it to someone else at a high level. This might be analogies or explanations using other programming concepts or concepts from a hobby.
_practice/2024-03-05.md:1. Practice using git to fix problem using a git command from the [patching or debugging section of the docs](https://git-scm.com/docs). Create a log of what you did using the history or git log into a file {index}`git_debug_story.md`. If you have a project in another class or another badge in this class that causes you to use one of these features in a real scenario, that can count. If not, for example, you could create a "bug" and then use bisect to find it.
_practice/2024-03-05.md:2. Create {index}`tagtypes.md` with the template below. Include an experiment that shows which if either type of tag creates a new git object. There are two types, try creating one of each a lightwight tag (provide only the tag name- what we did in class) and an annotated (provide a name and a message with `-m`).
_practice/2024-03-07.md:3. Analyze the xor hashing algorithm in the notes to determine which properties of a cryptographic hash are/not met. Include your analysis in {index}`xorhash.md`
_practice/2024-03-07.md:4. find 2 more real world examples of using other number systems (either different bases or different symbols and bases) **not mentioned in class** that are currently used. Describe the number system and its usage in {index}`numbers.md`. Include links to your sources and be sure that the sources are trustworthy.
_practice/2024-03-07.md:5. Calculate the maximum number of git objects that a repo can have without requiring you to use more than the minimum number of characters to refer to any object and include that number in {index}`gitcounts_scenarios.md` with a title `# Git counts`. Describe 3 scenarios that would get you to that number of objects in terms of what types of objects would exist. For example, what is the maximum number of commits you could have without exceeding that number, how many files could you have? How could you get to that number of objects in the fewest number of commits? What might be a typical way to get there? Assume normal git use with porcelain commands, not atypical cases with plubming commands. *If you get stuck, outline what you know and then request a review.*
_practice/2024-03-07.md:2. Learn more about how git is working on changing from SHA-1 to SHA-256 and answer the transition questions below {index}`gittransition.md`
_practice/2024-03-19.md:2. Write a bash script that updates your badges.json file and then generates your progress report using [courseutils](https://compsys-progtools.github.io/courseutils/index.html) *we will use this in lab on 3/25*
_practice/2024-03-21.md:1. Examine the IDE you use most and add {index}`frequentide.md` to your kwl with notes about which features it does/not have based on what you learned in the in-class activity.
_practice/2024-03-21.md:1. Try a new IDE and make some notes about how it was to learn in {index}`newide.md` What is easy? hard? What could you apply from the ones you already use? Were there features you had trouble finding?
_practice/2024-03-21.md:2. Configure your VS Code preferences to your github account. add {index}`settingssync.md` with a description of what settings you customized and synced and reflect on why this is an important feature and what prerequisites to it might be.
_practice/2024-03-26.md:1. Answer the following in {index}`hpc.md` of your KWL repo: (to think about how the design of the system we used in class impacts programming and connect it to other ideas taught in CS)
_practice/2024-03-26.md:3. Find 2 other encyrption algorithms that could be used wiht ssh (hint: try `man ssh` or [read it online](https://man7.org/linux/man-pages/man1/ssh.1.html)) and compare them in {index}`encyryption_compare`. Your comparison should be enough to advise someone which is best and why, but need not get into the details.
_practice/2024-03-26.md:4. Read through this [rsa encryption demo site](https://people.cs.pitt.edu/~kirk/cs1501/notes/rsademo/) site and use it to show what, for a particular public/private key pair (based on small primes) it would look like to pass a message, "It is spring now!" encrypted. (that is encypt it, and decrypt it with the site, show it's encrypted version and the key pair and describe what would go where). Put your example in {index}`rsademo.md`.
_practice/2024-03-28.md:1. On Seawulf, modfiy {index}`main.c` from class to accept the integer as a command line argument instead of via input while running the program. [See this tutorial for an example](http://crasseux.com/books/ctutorial/argc-and-argv.html).
_practice/2024-03-28.md:1. Write a bash script {index}`demo_test.sh` that runs your compiled program for each integer from 10 to 30 (syntax for a range is `{start..end}` so this would be `{10..30}`)
_practice/2024-03-28.md:2. Write an sbatch script, {index}`batchrun.sh` to run your script on a compute node and save the output to a file. The sbatch script should compile and link the program and then call the script. [see the options](https://web.uri.edu/hpc-research-computing/using-seawulf/#sbatch)
_practice/2024-04-02.md:1. File permissions are represented numerically often in octal, by transforming the permissions for each level (owner, group, all) as binary into a number. Add {index}`octal.md` to your KWL repo and answer the following. Try to think through it on your own, but you may look up the answers, as long as you link to (or ideally cite using jupyterbook citations) a high quality source.
_practice/2024-04-02.md:1. Run and examine how rect.hack and max.hack in the `nand2tetris/projects/05/` folder work. Make notes and answer the questions below in {index}`assemblyexplore.md`.
_practice/2024-04-04.md:1. Write a C program to compare values as doubles and as float (single precision/32bit) to see that this comparison issue is related to the IEEE standard and is not language specific. Make notes and comparison around its behavior and include the program in a code cell in {index}`cdouble.md`
_practice/2024-04-04.md:2. In {index}`floatexpt.md` design an experiment using the `fractions.Fraction` class in Python that shows helps illustrate why `.1*3 == .3` evaluates to `False` but `.1*4 ==.4` evaluates to `True`. Your file must include both code and interpretation of the results.
_practice/2024-04-09.md:1. While we saw many types of gates today, but we actually could get all of the operations needed using only NAND gates. Work out how to use NAND gates to implement a half adder and describe it in {index}`nandhalf.md`
_practice/2024-04-09.md:2. In {index}`addertypes.md` compare ripple adders and lookahead adders.
_practice/2024-04-09.md:3. Add {index}`bitwise.md` to your kwl and write the bitwise operations required for the following transformations (replace the `(_)` with a bitwise operator (`&, |, ^, >>, <<, ~`)):
_practice/2024-04-11.md:1. Read about [systems abstractions](https://cacm.acm.org/opinion/articles/259395-systems-abstractions/fulltext) in CACM and answer reflection questions below in {index}`systemsabstractions.md` based on the systems abstraction reading:
real 0m0.027s
user 0m0.003s
sys 0m0.013s
and at the bottom we see the timing results.
We get three times:
real: wall clock time, the total time that you wait for the the process to execute
user: CPU time in user mode within the the process, the time the CPU spends executing the process itself
sys: CPU time spent in the kernel within the process, the time CPU spends doing operating system interactions associated with the process
The real time includes the user time, the system time, and any scheduling or waiting time that that occurs.
22.6. Systems vs Application Programming#
most of you will do a lot more application programming than systems programming
knowing how the systems stuff works is important because you will need to interact with it.
22.7. Threading#
cd ..
nano sq_sum_threaded.c
This program is:
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
/* single global variable */
/* shared, accessible, modifiable by all threads */
int accum = 0;
void* square(void* x) {
int xi = (int)x;
accum += xi * xi;
return NULL; /* nothing to return, prevent warning */
}
int main(int argc, char** argv) {
int i;
pthread_t ths[20];
for (i = 0; i < 20; i++) {
pthread_create(&ths[i], NULL, square, (void*)(i + 1));
}
for (i = 0; i < 20; i++) {
void* res;
pthread_join(ths[i], &res);
}
printf("accum = %d\n", accum);
return 0;
}
this activity is from Matthew Wachs lecture notes
Then we can build the program.
gcc -pthread -Wall -g -o sqsum sq_sum_threaded.c -lm
sq_sum_threaded.c:10:12: warning: cast to smaller integer type 'int' from 'void *' [-Wvoid-pointer-to-int-cast]
int xi = (int)x;
^~~~~~
sq_sum_threaded.c:19:43: warning: cast to 'void *' from smaller integer type 'int' [-Wint-to-void-pointer-cast]
pthread_create(&ths[i], NULL, square, (void*)(i + 1));
^~~~~~~~~~~~~~
2 warnings generated.
We can both compile and link it at once and we get just a warning
and we can run the program
./sqsum
accum = 2870
We saw that different students got different answers.
We can use a for loop in bash to explore this further and figure out why.
./sqsum
accum = 2866
./sqsum
accum = 2866
./sqsum
accum = 2860
for i in {1..1000}
> do
> ./sqsum
> done | sort | uniq -c
this also uses some new bash commands:
sortorders all of the outputs of the 1000 runs of our programand
uniqwith the-coption counts how many times any given result appeart multiple times
Important
A few students got the same value for all 1000 trials, it is worth looking up why.
Making a PR here with a link to an explanation is worth a community badge.
Doing a more involved investigation here is a possible explore badge opportunity
1 accum = 2812
1 accum = 2825
1 accum = 2829
1 accum = 2833
5 accum = 2834
1 accum = 2841
1 accum = 2844
13 accum = 2845
1 accum = 2853
23 accum = 2854
9 accum = 2861
9 accum = 2866
11 accum = 2869
923 accum = 2870
So, this time I got the right answer most of the times, 923 out of 1000, but lots of other answers at least once.
To understand what happens, lets look at the following program, which should be an equivalent way to implement the body of the square function.
int temp = accum;
temp += x * x;
accum = temp;
In this one, we first copy the accum value to a temporary variable, then square the value and add that to temp, and then finally add that value back to accum. This should be equivalent to the program above, result wise.
Even though this is not how we wrote our program, this is actually what it has to do, as we spin out each process.
This table traces through what occurs in two threads.
// Thread 1 |
// Thread 2 |
Status |
|
|
now |
`temp2 += 2 * 2; |
now temp2 = 4 |
|
temp1 += 1 * 1; |
// temp1 = 1 |
|
accum = temp1; |
// accum = 1 |
|
accum = temp2; |
// accum = 4 |
So, what happens is each thread looks at the current value of accum and stores it to a thread-specific temporary variable. Each thread has its own memory, but they do all share the global variables.
Then thread 2 completes its calculation and updates temp2 and thread 1 updates temp1. So far everything is okay, but next thread 1 writes to accum and sets it to 1, and finally thread to writes to accum and makes it 4. The two values from the threads did not get added together, because thread 2 started before thread 1 finished.
So, we end up losing some of the values.
22.8. Locking#
We can instead change our square function. First we copy it
cp sq_sum_threaded.c sq_sum_locked.c
Then edit the copy
nano sq_sum_locked.c
so that the square function is like:
int accum = 0;
pthread_mutex_t accum_mutex = PTHREAD_MUTEX_INITIALIZER;
void* square(void* x) {
int xi = (int)x;
int temp = xi * xi;
pthread_mutex_lock(&accum_mutex);
accum += temp;
pthread_mutex_unlock(&accum_mutex);
return NULL; /* nothing to return, prevent warning */
}
This version uses something from the pthread library, to create a lock.
Now when it executes each thread will do the calculation part on it’s own time, possibly simultaneously. Then the lock part means that they will each take turns to add their value to the global variable accum.
then we build this:
gcc -pthread -Wall -g -o sqsuml sq_sum_locked.c -lm
sq_sum_locked.c:11:14: warning: cast to smaller integer type 'int' from 'void *' [-Wvoid-pointer-to-int-cast]
int xi = (int)x;
^~~~~~
sq_sum_locked.c:25:43: warning: cast to 'void *' from smaller integer type 'int' [-Wint-to-void-pointer-cast]
pthread_create(&ths[i], NULL, square, (void*)(i + 1));
^~~~~~~~~~~~~~
2 warnings generated.
./sqsuml
accum = 2870
./sqsuml
accum = 2870
./sqsuml
accum = 2870
for i in {1..1000}; do ./sqsuml; done | sort | uniq -c
1000 accum = 2870
time ./sqsum
accum = 2870
real 0m0.008s
user 0m0.002s
sys 0m0.004s
time ./sqsuml
accum = 2870
real 0m0.006s
user 0m0.002s
sys 0m0.004s
time ./sqsum
accum = 2866
real 0m0.009s
user 0m0.003s
sys 0m0.005s
time ./sqsuml
accum = 2870
real 0m0.007s
user 0m0.003s
sys 0m0.004s
This is a good topic to explore further for an explore badge. Under what conditions does the locking take more time? does it ever?
22.9. Prepare for Next Class#
Spend a few minutes thinking about what you know about memory and reading and writing files in programming. Make some notes about it (that you do not need to submit). (you’ll discuss this with classmates at the start of class)
22.10. Badges#
Update your KWL chart.
Simulate a more computationally intensive program using the
sleepfunction in C and compare the time of a threaded vs single threaded (ie serial, no intentional threading) version of the program. Include your two programs and the bash script to show how you tested it with notes on the performance in threaded.md (to better illustrate the impact of the threads)
Update your KWL chart.
Simulate a more computationally intensive program using the
sleepfunction in C and compare the time of a threaded vs single threaded (ie serial, no intentional threading) version of the program. Include your two programs and the bash script to show how you tested it with notes on the performance in threaded.md (to better illustrate the impact of the threads)Learn about the system libraries in two languages (one can be C or Python, one must be something else). Find the name(s) of the library or libraries. In systeminteraction.md summarize what types of support are shared or different? What does that tell you about the language?
Research examples of programs using multi-threading besides splitting up a single calculation for time reasons, include three examples in whymultithread.md.
Questions
What kind of tools did you use for a software defined radio?
I worked with matlab batch processing implemented the processing of the data from scratch with C.
Will RAID ever be 100% fail proof?
RAID configurations can be data failure proof as long as not too many drives die at the same time and that they are all replaced as soon as they fail.
Is the clock speed of a computer how fast the clock goes on and off? and is there ever an error that occours if the clock speed goes too slow?
It is the frequency of the clock signal we will learn more about next week.
Do you think this area in computer science/software engineering is harder than other fields like data science or web development?
I think they’re just different. Working with hardware is certainly a different pace.
Can these different types of ram not be included or are they in every computer?
most modern computers have cache, RAM, ROM, and solid state storage. these are implemented with different types of physical memory.
If a computer has extensive resources would it be more effcient to never use DRAM and only use SRAM?
This might be possible, but I am not sure.
What is EEPROM?
Electrically Erasable Programmable Read Only memory
How does knowing the hardware/internal components of the computer help improve one’s understanding of what they’re trying to achieve as a developer for something like a program?
It helps you think through how abstractions work and understanding what actually happens will help you deign more efficient code.
How much would it cost to fix a cable that a whale found itself tangled in?
the cable is mostly burried. It gets damaged mostly by anchors of ships.
Is ROM still used in modern computers?
Only for the very beginning of the boot sequence, but yes.
When does a kind of storage become absolete?
That is a good question, but I do not have a precise answer.
When they go down to set the transatlantic cable how long does it take to get them back up?
I do not know this and a quick search did not yeild results. Finding this is worth a commnity badge (could be expanded to an explore).
22.11. Experience Report Evidence#
22.12. Questions After Today’s Class#
22.12.1. Is there a way to limit my CPU to make those expected errors occur?#
Use an un optimized compiler.
22.12.2. is there any particular reason that the time that users notice was named real instead of user? i feel like that is built to cause confusion#
I cannot find a good reason why
22.12.3. Do programmers regularly use this time command to see the efficiency of their programs?#
It can be. It can also be done wiht more sophisticated tools
22.12.4. For very coding complicated programs is coding things to happen simultaneously across multiple threads an expected skill?#
Yes.
22.12.5. What other ways can you prevent a race condition?#
Locking the varialbe is pretty much it, or do not use a global variable if you do not need it.
22.12.6. If there are 20 threads but only 4 cores, will it queue the threads after the first four?#
Yes
22.12.7. How does the computer count the three times?#
this is a good explore topic
22.12.8. How common is it for bugs to be caused due to race conditions?#
this is hard to know.