file_format: mystnb kernelspec: name: python3

24. How does timing work in a computer?

24.1. Final Grading

The last day to submit or revise work is December 14. Final grading begins the following day. Final grading still include the “request changes” feedback but revisions will not be considered toward your grade.

I will go through your whole repo and post an issue with your final grade. You can write back to point out if you think there is an error until December 20 and I’ll update the grade before submitting.

24.2. IDEA incentive

If the course reaces 75% final response rate then, the free corrections will extend to final grading.

If this is met, after you receive your final grading work you can respond to gift free gift suggestions until December 20.

24.3. 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

24.4. Control Unit

The control unit converts binary instructions to signals and timing to direct the other components.

24.4.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.

24.4.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.

24.5. 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.

24.6. Execution Times

cexample			github-inclass-fa23-brownsarahm
fa23-kwl-brownsarahm		nand2tetris
fall2023			test
ghic				tiny-book

We’ll cd into the course website repo.

and update it

remote: Enumerating objects: 1188, done.
remote: Counting objects: 100% (903/903), done.
remote: Compressing objects: 100% (156/156), done.
remote: Total 1188 (delta 746), reused 899 (delta 744), pack-reused 285
Receiving objects: 100% (1188/1188), 76.41 MiB | 3.06 MiB/s, done.
Resolving deltas: 100% (931/931), completed with 21 local objects.
...
 create mode 100644 notes/2023-11-21.md
 create mode 100644 notes/2023-11-28.md
 create mode 100644 notes/2023-11-30.md

Note

the ouput above is truncated

We can use the time command to see how long a command takes to run.

and we get results of the command

_practice/2023-09-12.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 and how, if at all, it changes how you think about debugging and learning to program.
_practice/2023-09-12.md:2. map out your computing knowledge and add it to your kwl chart repo in a file called {index}`prior-knowledge-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. 
_practice/2023-09-14.md:3. Try using setting up git using your favorite IDE or GitHub Desktop. Make a file {index}`gitoffline.md` and include some notes of how it went. Was it hard? easy? what did you figure out or get stuck on? Is the terminology consistent or does it use different terms?
_practice/2023-09-14.md:2. **lab** Explore the difference between git add and git commit: try committing and pushing without adding, then add and push without committing. Describe what happens in each case in a file called {index}`gitcommit_tips.md`. Compare what happens based on what you can see on GitHub and what you can see with git status. Write a scenario with examples of how a person might make mistakes with git add and commit and what to look for to get unstuck. 
_practice/2023-09-19.md:1. Create a merge conflict in your github in class repo 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}`ide_merge_conflict.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)
_practice/2023-09-21.md:2. Get set up so that you can pull from the introcompsyss/fall2023 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 `fall2023/.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/2023-09-21.md:4. For extra practice, re/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/2023-10-03.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/2023-10-03.md:4. Find the hash of the blob object that contains the content of your {index}`gitislike.md` file and put that in the comment of your badge PR for this badge. 
_practice/2023-10-05.md:1. Add to your {index}`software.md` a section about if that project does or does not adhere to the unix philosophy and why.  You can see what badge it was previously assigned in and the instructions [on the KWL file list](https://introcompsys.github.io/fall2023/genindex.html).
_practice/2023-10-05.md:2. create {index}`methods.md` and answer the following:
_practice/2023-10-12.md:2. 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. 
_practice/2023-10-12.md:3. 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/2023-10-17.md:1. 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/2023-10-17.md:1. find 2 more real world examples of using other number systems (either different bases or different symbols and bases) that are current. Describe them in {index}`numbers.md`
_practice/2023-10-17.md:2. Calculate the maximum number of git objects that a repo can have without needing 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/2023-10-19.md:1. Use your github-inclass repo to create a scenario where you can fix a 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}`gitstory.md`. If you have a project in another class or another badge in this class that causes you to use one in a real scenario, that can count.  If not, for example, you could create a "bug" and then use bisect to find it.  
_practice/2023-10-19.md:2. Create {index}`tagtypes.md`  with the template below.
_practice/2023-10-24.md:2. Write a bash script that you can run in your group repo to generate a file with a list of all of your PRs and PR reviews (you may go in and assign yourself to these PRs to make this easier). Save the script as {index}`groupcontributions.sh` and its output as {index}`group_contributions-YYYY-MM-DD.md` in your KWL repo. 
_practice/2023-10-31.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/2023-10-31.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/2023-11-02.md:2. Install [ gcc](https://gcc.gnu.org/install/) locally and practice using it.  Repeat steps we did in class on your computer and then change the order of parameters; try skipping steps to produce errors, etc. Export the list of variations you tried and summarize what you learned as a list of tips and reminders on what the parameters do/why/when you would need them (or not) in {index}`gcctips.md`.  (to reinforce what we learned)
_practice/2023-11-02.md:3. Write two short programs that do the same thing in different ways and compile them both to assembly (eg using a for vs while loop to sum numbers up to a number). Check the assembly to see if they produce the same thing or if it's different. Save your code (in code blocks) and notes about your findings in {index}`assemblycompare.md`
_practice/2023-11-07.md: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/2023-11-07.md:5. 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/2023-11-07.md:6. 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/2023-11-09.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/2023-11-09.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/2023-11-14.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/2023-11-16.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/2023-11-16.md:2. In {index}`addertypes.md` compare ripple adders and lookahead adders.
_practice/2023-11-16.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/2023-11-21.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/2023-11-21.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/2023-11-28.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.018s
user	0m0.002s
sys	0m0.011s

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.

24.7. Threading

You can run the following on your local computer if you have gcc or use seawulf or a codespace otherwise. To check if you have gcc try the command.

clang: error: no input files

We’ll move out of the course website first.

Next we’ll open nano to edit.

Note

this activity is from Matthew Wachs lecture notes

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;
}

Then we can build the program.

We can both compile and link it at once and we get just a warning

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));
                                          ^
1 warning generated.

and we can run the program

accum = 2870

and again

accum = 2821

and we see we got different answers.

We saw that different students got different answers.

We can use a for loop in bash to explore this further and figure out why.

this also uses some new bash commands:

• sort orders all of the outputs of the 1000 runs of our program

• and uniq with the -c option counts how many times any given result appear multiple times

in the results we see:

   1 accum = 2482
   1 accum = 2645
   1 accum = 2749
   1 accum = 2770
   1 accum = 2789
   1 accum = 2817
   1 accum = 2829
   1 accum = 2830
   4 accum = 2834
  13 accum = 2845
  12 accum = 2854
   1 accum = 2857
   6 accum = 2861
  14 accum = 2866
   2 accum = 2869
 940 accum = 2870

We see the correct answer occured most of the time, but not all of the times.

So, this time I got the right answer most of the times, 956 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
int temp1 = accum;	int temp2 = accum;	now temp1 = temp2 = 0
	`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.

24.8. Locking

We can instead change our square function. First we copy it

Then edit the copy

The edited file is as follows:

#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>

/* single global variable */
/* shared, accessible, modifiable by all threads */
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 */
}

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 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:

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));
                                          ^
1 warning generated.

Now we all get the same result

accum = 2870

Even 1000 full times.

1000 accum = 2870

25. Does the locking one take longer?

accum = 2870

real	0m0.008s
user	0m0.003s
sys	0m0.005s

accum = 2870

real	0m0.008s
user	0m0.003s
sys	0m0.006s

accum = 2870

real	0m0.006s
user	0m0.002s
sys	0m0.004s

accum = 2870

real	0m0.008s
user	0m0.003s
sys	0m0.005s

We get inconsistent results at first glance. This is a good topic to explore further for an explore badge. Under what conditions does the locking take more time? does it ever?

25.1. Prepare for Next Class

3. Preview the Stack Overflow Developer Survey Technology section parts that are about tools. Create dev_insights.md with 3-5 bullet points for discussion. These can be facts you found most interesting or questions you have based on the results (it can be clarifying or deeper questions)

25.2. Review today’s class

1. Update your KWL chart.

2. Simulate a more computationally intensive program using the sleep function 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)

25.3. More Practice

1. Update your KWL chart.

2. Simulate a more computationally intensive program using the sleep function 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)

3. 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?

4. Research examples of programs using multi-threading besides splitting up a single calculation for time reasons, include three examples in whymultithread.md.

25.4. Experience Report Evidence

append your command history to your experience report.

25.5. Questions After Today’s Class

25.5.1. Will we be using threads more going foward, or is this a brief overview?

They will come up in CSC412, just a brief overview for this course.

25.5.2. For what situation would we need to use each of these times?

The real time is probably mostly a sanity check, but the other two you can have some control over. Your code is the user time explicitly, but you can also controls some of the overleaf.

25.5.3. If the clock speed of a cpu changes, can that affect things computation wise?

Yes.

25.5.4. Is it generally better to parallelize everything using threads?

Parallizing is good when it makes sense.

25.5.5. I have a CPU on my desktop that is multithreaded. Am I correct in saying multhreaded means a CPU take each core and splits them into two threads? My CPU is an 8-core, 16-thread CPU.

Yes

25.5.6. What other ways to solve the race condition are there besides locking and async/await?

This is a good explore badge topic

25.5.7. Even though the program we ran today were fast in human time, are there programs that will take a lot longer, maybe seconds or even minutes of human time?

Yes! Computational programs can take a lot longer. For example machine learning algorithms can take minutes to train on relatively tractable problems and hours-weeks to train for complex problems.

25.5.8. Why did the bash for loop not run even with the program already compiled and then worked after?

I am not sure why and I cannot replicate it, so I may never know.

25.5.9. What sorts of programming often require multithreading (such as graphics, machine learning, embedded, etc)?

This is in the practice badge for today.

25.5.10. Where could we use measuring clock speed in a developer sense?

You might have a constraint of how long your code has to run. You might also want to measure the time so that you can cut it down.

25.5.11. How useful would this be in being a computer engineer designing CPUs?

Essential, you need to know how fast it is in order to figure out how to design the rest. You would need to know the duration of actual calculations in order to set the clock speed.

25.5.12. Also for some reason I got an error that went along the lines of this when compiling main.c:3:21: fatal error: pthread.h: No such file or directory?

That means that you do not have the pthread library.