How does timing work?

25. How does timing work?#

26. How do clocks impact computing?#

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

26.2. Control Unit#

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

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

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

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

26.4. Execution Times#

ls

example				seawulf
github-in-class-brownsarahm-1	test
kwl				testobj.md
nand2tetris			tiny-book

Let’s clone the course website to have a set of files.

git clone https://github.com/introcompsys/spring2023.git

Cloning into 'spring2023'...
remote: Enumerating objects: 4545, done.
remote: Counting objects: 100% (887/887), done.
remote: Compressing objects: 100% (202/202), done.
remote: Total 4545 (delta 699), reused 845 (delta 682), pack-reused 3658
Receiving objects: 100% (4545/4545), 103.44 MiB | 716.00 KiB/s, done.
Resolving deltas: 100% (3224/3224), done.

time grep "index" spring2023/

grep: spring2023/: Is a directory

real	0m0.032s
user	0m0.001s
sys	0m0.015s

time grep "index" spring2023/_practice/*

and we get results

spring2023/_practice/2023-01-26.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.
spring2023/_practice/2023-01-26.md:3. [complete the syllabus quiz](https://forms.gle/sDpJCYEHNTSW2w2w7). If you get less than 100%, submit an FAQ for the course website in your KWL repo in a file named {index}`syllabus-faq.md` about something that confused you with your best guess at the correct answer. If you get 100%, make a note in your badge PR.
spring2023/_practice/2023-01-31.md:2. 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. 
spring2023/_practice/2023-02-02.md:2. Download the course website repo via terminal. Append the commands used to a {index}`terminalwork.md`  
spring2023/_practice/2023-02-02.md:3. 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 your {index}`gitcommit.md`. Compare what happens based on what you can see on GitHub and what you can see with git status. 
spring2023/_practice/2023-02-09.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. 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)
spring2023/_practice/2023-02-14.md:2. Add to your {index}`software.md` a section about if that project does or does not adhere to the unix philosophy and why. 
spring2023/_practice/2023-02-14.md:3. create {index}`methods.md` and answer the following:
spring2023/_practice/2023-02-21.md:1. Practice with git log and redirects to write the commit history of your main branch for your kwl chart to a file {index}`gitlog.txt` and commit that file to your kwl repo.
spring2023/_practice/2023-02-21.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)
spring2023/_practice/2023-02-23.md:2. Read 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 {index}`gitplumbingdetail.md`. 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. 
spring2023/_practice/2023-02-23.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. 
spring2023/_practice/2023-03-02.md:1. use `git cat-file` over the objects to draw a graph diagram of your current status in your test directory include your drawing in {index}`test_repo_map.md` using [mermaid](https://github.blog/2022-02-14-include-diagrams-markdown-files-mermaid/) syntax to diagram it. Name each node in your graph with 5-7 characters of the hash and the type. eg `0c913 commit`
spring2023/_practice/2023-03-02.md:1. Update your diagram in {index}`test_repo_map.md` after the following. 
spring2023/_practice/2023-03-07.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`
spring2023/_practice/2023-03-09.md:2. Write a bash script that can generate a file in your KWL repo with a list of all of your PRs and PR reviews. Save the script as {index}`groupcontributions.sh` and its output as {index}`group_contributions-YYYY-MM-DD.md` 
spring2023/_practice/2023-03-21.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-practice.md` to your KWL repo and answer the following.
spring2023/_practice/2023-03-28.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.
spring2023/_practice/2023-03-28.md:1. Try out/learn about one of the following languages that you have not used before, do something small that is typical of that language (eg a toy data analysis in R): [R](https://www.r-project.org/), [Julia](https://julialang.org/), [Clojure](https://clojure.org/guides/getting_started), [Stan](https://mc-stan.org/), [Go](https://go.dev/).  Try to use official documentation only to figure out a toy task to do.  Answer the following questions in {index}`languagelearning.md`:
spring2023/_practice/2023-04-04.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)
spring2023/_practice/2023-04-04.md:8. 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)
spring2023/_practice/2023-04-06.md:1. Add {index}`bitwise.md` to your kwl and write the bitwise operations required for the following transformations:
spring2023/_practice/2023-04-06.md:3. Create {index}`readingbytes.md` and answer the following:
spring2023/_practice/2023-04-06.md:4. Read about integer overflow and describe what it is, use an example assuming an 8 bit system, and  how integer overflow is handled in Python, C, Javascript, and one other language of your choice in {index}`overflow_languages.md` 
spring2023/_practice/2023-04-18.md:4. Answer reflection questions below in {index}`systemsabstractions.md` based on the systems abstraction reading:

real	0m0.023s
user	0m0.004s
sys	0m0.015s

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.

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

26.6. Threading#

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

Then we can build the program.

gcc -pthread -Wall -g -o sqsum sq_sum_threaded.c -lm

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

sq_sum_threaded.c:22: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

./sqsum

accum = 2870

./sqsum

accum = 2866

./sqsum

accum = 2821

To confirm, let’s do it in python:

python

Python 3.8.3 (default, Jul  2 2020, 11:26:31) 
[Clang 10.0.0 ] :: Anaconda, Inc. on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> sum([i**2 for i in range(1,21)])
2870
>>> exit()

We saw that different students got different answers.

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

for i in {1..1000}
> do
> ./sqsum
> done | sort | uniq -c

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 appeart multiple times

then we get results:

accum = 2184
accum = 2508
accum = 2509
accum = 2581
accum = 2745
accum = 2805
accum = 2806
accum = 2809
accum = 2821
accum = 2825
accum = 2830
accum = 2834
accum = 2841
accum = 2844
accum = 2845
accum = 2854
accum = 2861
accum = 2866
accum = 2870

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.

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

same warning

sq_sum_locked.c:27: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.

./sqsuml

accum = 2870

Now we all get the same result

for i in {1..1000}; do ./sqsuml; done | sort | uniq -c

1000 accum = 2870

and in our experiment, it comes out the same every time

27. Does the locking one take longer?#

time ./sqsum

accum = 2861

real	0m0.173s
user	0m0.002s
sys	0m0.005s

time ./sqsuml

accum = 2870

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

Here it looks like it is actually the same user time, and a litte bit less system time.

time ./sqsum

accum = 2834

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

time ./sqsuml

accum = 2870

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

A second time it comes out a little slower in user and same in system.

Note

This is a good topic to explore further for an explore badge. Under what conditions does the locking take more time? does it ever?

27.1. Review today’s class#

Update your KWL chart.
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)

27.2. Prepare for Next Class#

(optional, get a head start on the final review/practice badges) Bring 2 multiple choice questions about computer systems, machine representation, or building code to class.
(optional, community badge opportunity) Try out the Pycharm extenstion created by one of your classmates as a build badge. You can download it by searching “gcc integration” in pycharm directly in the plugin marketplace or by following the instructions on the documentation website. If you succeed, comment on your prepare issue with which technique (pluging marketpalce or manual) you used to install it and tag Professor Brown. If it does not work, open an issue that describes what you did, what happened, and what you expected instead and link to that issue on your prepare issue and tag Professor Brown for the community badge. (write a long full review of the extension comparing it to similar available tools for an explore badge)

27.3. More Practice#

Update your KWL chart.
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)
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.

27.4. Experience Report Evidence#

cat your experiment loop result and timing results to a file.