ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Essential computer architecture concepts
by
Marcel Turcotte
Version January 6, 2020
Preambule
Preambule
Overview
Overview
Essential computer architecture concepts
We review the essential concepts of computer architecture: von Neumann’s model,
memory, and compilation. We simulate the execution of a machine language program
using a didactic model of a microprocessor.
General objective :
This week you will be able to describe the execution of the machine program in your
own words.
1 49
Preambule
Learning objectives
Learning objectives
Explain in your own words the concepts of memory, compilation, and variable.
Simulate the execution of a simple machine program.
Readings:
–
2 49
Preambule
Plan
Plan
1 Preambule
2 Introduction
3 49
Introduction
Prerequisites
You must master the following concepts:
Predefined data types and arrays
Control structures:
such as if, for, while. . . ;
Procedural abstraction :
i.e. how to decompose a problem into sub-problems.
4 49
Why so many programming languages?
Introduction
Computer architecture
von Neumann
The architecture of modern computers is based on a model proposed by (John) von
Neumann (1945).
memory: contains the instructions and the data
alu: arithmetic and logic unit
cu: the control unit decodes the instructions
m
e
m
o
ry
Processing
Unit
6 49
Memory model
Can be seen as a huge array,
each cell contains a zero or one
(binary digit — bits);
…
0 1 1 0
7 49
Memory model
Each byte (group of 8 bits) has a unique (distinct) address;
Bytes are grouped into words
Some types of data require more than one byte.
…
0123
0
4
8
8 49
Memory model
This type of memory is said to be direct access
(Random Access Memory)
The access time to the memory cells is uniform and constant.,
On the order of 5 to 70 nanoseconds (nano = 10−9)
…
0123
0
4
8
9 49
Computer architecture
Simplified model of a microprocessor (TC1101) and its assembly language.
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
10 49
Mnemonics, opCodes, description
LDA 91 load x
STA 39 store x
CLA 08 clear (a=0, z=true, n=false)
INC 10 increment the accumulator (modifies z and n)
ADD 99 adds x to the accumulator (modifies z and n)
SUB 61 subtracts x from the accumulator (modifies z and n)
JMP 15 unconditional branching to x
JZ 17 branch to x if z==true
JN 19 branch to x if n==true
DSP 01 displays the stored at x
HLT 64 halt
11 49
TC1101 instructions
This microprocessor supports 11 instructions.
In the previous table, you’ll find on the left side the instruction name, in the center the
machine code, and on the right side the instruction description.
Instructions with an even code have no parameters, whereas instructions with an
odd have one.
The term operand is used to name the parameter of an instruction.
The operand is a memory address.
12 49
Registers
Registers are specialized memory units.
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
13 49
Control unit
The control unit orchestrates the execution of the instructions.
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
14 49
Arithmetic and logic unit (ALU)
The Arithmetic and logic unit (ALU) performs the calculations.
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
15 49
Bus
Information is transferred from one unit to another on buses.
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
16 49
Data bus
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
17 49
Address bus
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
18 49
Control bus
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
19 49
Transfer to the memory
In order to transfer a value v from the microprocessor to the memory address x :
1. put v into the memory data register (MDR),
2. put x into the memory address register (MAR),
3. put status bit RW to false,
4. activate the control line «access_memory».
20 49
00
91
08
10
39
09
00
64
10
99
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
11
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
00 09
11
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
00 09
11
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
F
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
11
00 09
11
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
F
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
Transfer from the memory
In order to transfer a value from the (memory) address x to the microprocessor:
1. put the value x into the memory address register (MAR),
2. put the status bt RW to true,
3. activate the control line «access_memory»
4. the memory data register (MDR) now contains a copy of the value found at
memory location x .
26 49
00
91
08
10
39
09
00
64
10
99
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
00 08
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
00 08
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
T
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
00
91
08
10
39
09
00
64
10
99
00 08
10
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
T
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
Fetch-decode-execute cycle
1. transfer:
1.1 transfer the OPCODE,
1.2 increment PC,
2. based on OPCODE transfer the operand:
2.1 transfer the first byte,
2.2 increment PC,
2.3 transfer the second byte,
2.4 increment PC,
3. execute.
31 49
Compilation
The programs, sequences of statements from a high-level programming language, are
translated (compiled) into a low-level language (assembler, machine code), directly
interpretable by the hardware.
The expression y = x + 1 is translated to assembly :
LDA X
INC
STA Y
HLT
which is the translated to machine code:
91 00 08 10 39 00 09 64 10 99
32 49
The expression y = x + 1 is translated to assembly :
LDA X
INC
STA Y
HLT
which is then translated to machine code :
91 00 08 10 39 00 09 64 10 99
00
91
08
10
39
09
00
64
10
99
ALU
Control
MAR
MDR
OpCode OpAddr A
PC
H
Z
N
R/W
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
9999
Memory Microprocessor
Functional Units of the TC-1101
PC (2 bytes): Program Counter , one 2 bytes register that contains the address of the
next instruction to be executed;
opCode (byte): instruction register (sometimes called IR), contains the OPCODE of the
current instruction;
opAddr (2 bytes): the operand of the current instruction. The operand is always an
address. Some instructions necessitate the value found at the address
designated by the operand — this value is not transferred by the basic cycle,
but needs to be transferred during the execution of the instruction (see step
3 of the cycle and the description of each instruction below);
34 49
Functional Units of the TC-1101
MDR (byte): Memory Data Register. A value transferred (read/written) from the
memory to the processor (or vice-versa) is always stored in this registered;
MAR (2 bytes) : Memory Address Register . This register contains the memory address
of a value to be read or to be written;
A (byte): Accumulator. All the arithmetic operations use this register as an operand
and also to store their result;
35 49
Functional Units of the TC-1101
H (bit): status bit “Halt”. This bit is set by the instruction halt (hlt). If the bit is
true the processor stops at the end of this cycle;
N (bit): status bit “Negative”. Arithmetic operations set this bit to true whenever
they produce a negative result. Some operations are not affecting the value
of this bit, therefore its value does not always reflect the content of the
accumulator;
Z (bit): status bit “Zero”. Arithmetic operations set the value of this bit to true
whenever the result is zero. Some operations do not affect the content of
this bit, therefore, its value does not always reflect the content of the
accumulator;
36 49
Functional Units of the TC-1101
RW (bit): status bit “READ/WRITE”. A value true means a value must be read
(fetched) from the memory and transferred to MDR. A value false signifies
that a value must be transferred from MDR to the memory.
37 49
Assembly language
Assembly language is not very expressive.
Each microprocessor has its own assembly language. Programs are thus not
portable from one computer to another.
38 49
High-level programming languages
High-level programming languages are expressive.
Generally, a high-level programming language is also portable.
39 49
Paradigms
Imperative or procedural
Object-oriented
Declarative
Functional
Logic
Constraint
40 49
Why Java?
Why Java?
42 49
Why Java?
1 Java 17%
2 C 9%
3 C++ 6%
4 C# 4%
5 Python 4%
6 Basic 3%
7 JavaScript 3%
8 Perl 3%
9 Assembly 3%
10 PHP 3%
TIOBE Programming Community Index
43 49
http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html
Why Java?
1 JavaScript
2 Java
3 PHP
4 Python
5 C#
5 C++
5 Ruby
8 CSS
9 C
10 Objective-C
The RedMonk Programming Language Rankings: January 2016
44 49
Why Java?
Java is popular, but I don’t know any application written in Java.
The server side of many Web applications and services.
Mobile applications (mobile phones)
2015 Top Trending Careers in Tech: Java Developer
info.theladders.com/career-advice/top-market-trends-in-tech
45 49
http://info.theladders.com/career-advice/top-market-trends-in-tech
Why Java?
« According to a report from NetApplications, which has measured browser usage data
since 2004, Oracle’s Java Mobile Edition has surpassed Android as the #2 mobile OS
on the internet at 26.80%, with iOS at 46.57% and Android at 13.44%. And the trend
appears to be growing. Java ME powers hundreds of millions of low-end ’feature phones’
for budget buyers. In 2011, feature phones made up 60% of the install base in the
U.S. »
Slashdot
3 janvier 2012
http://bit.ly/xSk5pN
46 49
http://bit.ly/xSk5pN
Why Java?
Writing programs using C requires discipline
(managing memory, manipulating pointers, etc.)
Java is an excellent vehicle for teaching
(interface, single inheritance, generic types. . . )
If you master Java, learning other object-oriented or imperative programming
languages will be simple.
47 49
Why Java?
Source: https://commons.wikimedia.org/wiki/File:Netflix_logo.svg
https://go.java/netflix.html
48 49
https://commons.wikimedia.org/wiki/File:Netflix_logo.svg
https://go.java/netflix.html
Next module
Data types
49 / 49
Division by successive subtractions
[1] CLA
STA Quot
[2] LDA X
[3] SUB Y
[4] JN [7]
[5] STA Temp
LDA Quot
INC
STA Quot
LDA Temp
[6] JMP [3]
[7] ADD Y
[8] STA Rem
[9] DSP Quot
[10] DSP Rem
[11] HLT
X BYTE 25
Y BYTE 07
Quot BYTE 00
Rem BYTE 00
Temp BYTE 00
Division: code machine
[1] CLA
STA Quot
[2] LDA X
[3] SUB Y
[4] JN [7]
[5] STA Temp
LDA Quot
INC
STA Quot
LDA Temp
[6] JMP [3]
[7] ADD Y
[8] STA Rem
[9] DSP Quot
[10] DSP Rem
[11] HLT
X BYTE 25
Y BYTE 07
Quot BYTE 00
Rem BYTE 00
Temp BYTE 00
⇒
08
39 00 44
91 00 42
61 00 43
19 00 29
39 00 46
91 00 44
10
39 00 44
91 00 46
15 00 07
99 00 43
39 00 45
01 00 44
01 00 45
64
25
07
00
00
00
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
D. J. Barnes and M. Kölling.
Objects First with Java: A Practical Introduction Using BlueJ.
Prentice Hall, 4e edition, 2009.
P. Sestoft.
Java Precisely.
The MIT Press, second edition edition, August 2005.
Marcel Turcotte
Marcel.
School of Electrical Engineering and Computer Science (EECS)
University of Ottawa
Marcel.
Preambule
Overview
Learning objectives
Plan
Introduction
Computer architecture
Appendix