Flashcards
Week 10
Cards in this deck (77)
- 1What should a software engineer studyThe first subject is machine organisation (elementary computer architecture)
The second subject to study is assembly language programming
The third important subject is basic compiler construction - 2The first subject is machine organisation (elementary computer architecture)Since real programs execute on real machines, you need to understand
how real machines operate to write efficient code for those machines - 3The second subject to study is assembly language programming– Though few programmers use assembly language for application
development, its knowledge is critical if you want to make the connection
between a high-level language and the low-level CPU
– It doesn't matter which assembly language you learn nor does it matter
which CPU's instruction set you study, what you really need to learn are
the basic operational costs of computation - 4The third important subject is basic compiler constructionTo learn how compilers translate high-level language statements into
machine code - 5SyntaxSyntax is the form of a program
Various languages have different names for the same thing - 6Syntax errorsCompilers check that the syntax is right, but in English if you spell a word
wrong or have a missing comma you’ll (probably) still be understood
Can't a compiler be equally forgiving?
– Some experiments with compilers guessed what the programmer meant
– It was a disaster: the compiler nearly always guessed correctly but
occasionally it would guess wrong - 7operator precedence• Expressions can contain many operations, but the computer can do only one
operation at a time
• We can make the operations explicit by using parentheses around each
operation
• You don't have to write the parentheses, but the compiler needs to know
where they go! - 8Deeper example of syntax: ambiguity• A language is ambiguous if a sentence in the language can have two
different meanings
• English is full of ambiguity
• Programming languages are designed to avoid ambiguity, most of the time
• If ambiguity is possible, the compiler needs to know how to resolve it, and so
does the programmer - 9How do programming languages prevent ambiguity?In Python the structure of the program is determined by indentation
Some languages use braces to indicate structure (e.g. C, Java) - 10goto• Usually programs are more readable and more reliable if written with while
loops, if-then-elif-elif-else, for loops, and similar high-level constructs
• Programs that jump around randomly with goto statements are harder to
understand, and likely to contain bugs
• This gave the goto statement a bad reputation - 11goto spelled differently• Some programming languages provide restricted forms of goto
– break
– continue
• These are goto statements without a label, but with a predefined destination
they go to
– Advantage: you may recognise the pattern being used by a programmer
– Disadvantage: you need to know exactly where your goto goes - 12The break statement• Break is a goto that goes to the end of the innermost loop it's in
• In Python you can have an else clause to execute when a for or while loop
finishes, but this is skipped if you terminate the loop with break - 13The continue statement• It's a way of staying in the loop but skipping the statements after the
continue
• Warning! Several programming languages have a statement that is spelled
continue - 14Semantics• Semantics means the meaning
• The semantics of a language is what a program in the language means
• The semantics of a program is the meaning of the program - 15How is the semantics of a language defined? Using natural language to describe it– Vague description in English of what each construct does
– A carefully written description in English, as precise as possible - 16Using mathematics or program transformation Denotational semanticsa precise mathematical specification; given a
program, it gives a mathematical function from program inputs to outputs - 17Using mathematics or program transformation Operational semanticsgives a sequence of reduction rules that give a
precise model of the program's execution - 18Using mathematics or program transformation Transformational semanticsa translation from a program into a
simpler language, where the semantics is assumed to be clear - 19Why do the translation from high to low level?• This is the semantics of the high-level constructs
• It explains precisely what the high-level means
• It makes explicit the execution time of the construct
• The low level is very close to assembly language - 20CompilersA compiler is a software application that performs this translation automatically
The compiler makes programming easier by allowing you to think about your
algorithm more abstractly, without worrying about all the details of the
machine - 21source codeThe original high level language program is called the source code
– It's what the programmer writes - 22object codeThe final machine language program which the compiler produces is called
the object code
– It's what the machine executes - 23Compilation• A compiler translates statements in a high-level language into assembly
language
• In developing an assembly language program, it's best to begin by writing
high level pseudo-code (this becomes a comment) and then translate it
• This approach helps keep the program readable, and reduces the likelihood
of getting confused
• Each kind of high-level statement corresponds to a standard pattern in assembly language - 24code generationThe program is finally translated to assembly language
- 25How a compiler worksThe compiler reads the source program, checks its syntax, and analyses its
structure
Then it checks the types of all the variables and procedures
Most advanced compilers translate the program to an intermediate “goto
form”, just as we are doing
The program is finally translated to assembly language: “code generation”
The assembler translates the assembly language to machine language - 26intermediate “goto form"Most advanced compilers translate the program to an intermediate “goto
form”, just as we are doing - 27Major tasks in compilationParsing
Type checking
Optimisation
Code generation - 28Parsingcheck the source program for correct syntax and work out the program structure
- 29Type checkingwork out the data type of each variable (integer, character,
etc) and
– Make sure the variables are used consistently
– Generate the right instructions for that data type
This eliminates one of the commonest kinds of error in software - 30Optimisationanalyse the program to find opportunities to rearrange the
object code to make it faster - 31Code generationproduce the actual machine instructions
- 32TypesType checking is one of the most important tasks the compiler performs
There are many data types supported by a computer
The computer hardware works on words, and the machine does not know
what data type a word is
It's essential to use the right instruction, according to the data type - 33Write programs at a high level– Write conditionals using if-then or if-then-else
– Write loops using the most appropriate construct
– Avoid goto statements (and break statements, if the language has)
– Use a straightforward style that is easy to read
Every rule has some rare exceptions, but these are good principles - 34Use patterns to translate to low level• Low level algorithm contains just
– Assignment statements
– goto label
– if b then goto label
• Each high level construct is translated to low level using a fixed pattern
• Include the low level code in your program, as full line comments after the
high level code - 35Practical programming tip• Write the high level algorithm
– Hand execute it to be sure it's correct
– Type it into your file, as full line comments
• Translate it to low level form
– Hand execute it to be sure it's correct
– Type it into your file, as full line comments
• Duplicate the low level code (copy and paste)
– Now go through the second copy of the low level code, and insert the
assembly language after each statement
– Hand execute it to be sure it's correct
• Run the assembly program on the emulator, in single step mode, and check
that the program does what you predicted in your hand execution - 36Atoms– Nucleus: protons with positive charge and neutrons with neutral charge
– Electrons have negative charge - 37Electron Shells– Electrons are not randomly in orbit around the nucleus, they are grouped
into shells (as spheres at some distance from the nucleus)
– Each shell has an ideal number of electrons that will fit into it, and the
atom “likes” to have the outer shell filled to be stable - 38Covalent Chemical BondsChemistry is about how atoms stick together to form chemical bonds to form
molecules
– Two atoms with partially filled outer shells can “share” some electrons, and the effect is filling the shell of both atoms (they bond together) - 39InsulatorsIf an atom has just enough electrons to fill the outer shell exactly, then electricity (moving electrons) can’t go through it
- 40ConductorsIf an atom has only a few electrons in a big shell far from the nucleus, it is easy to move them when applying an electric field (electric current)
- 41Semiconductors• Halfway between an insulator and a conductor: Silicon is a semiconductor
• In a Silicon atom its outermost shell has 4 electrons (not strongly attracted)
• So an atom could form covalent bonds with its neighbours - 42silicon crystalIf every Silicon atom has 4 neighbours it is formed a silicon crystal, which
is a good insulator - 43Doped SiliconWe can “dope” the Silicon
– Doping is the process of adding impurities (a chemical substance) to a pure silicon crystal to alter its behaviour (electrical conductivity)
The more impurities are added, the greater the number of more or fewer electrons, resulting in an increase in conductivity - 44we could take a silicon crystal and replace a few of the silicon atoms with Boron (B) or Phosphorous (P)– This would give either one more or one fewer electrons in the outer shell
– And that means that an electric field can more easily get some of those
electrons moving, since the outer shell is not completely stable - 45N-type silicona semiconductor with negative charge carriers
– Called free electrons
- 46P-type silicona semiconductor with positive charge carriers
– Called holes (spots where an electron would like to be but is not) - 47Junctions
- 48Forward Biased Junction
- 49Reverse Biased Junction
- 50The Junction Diode• A diode allows current to flow across it one direction but not the other
• A PN junction does exactly that!
• The PN junction diode is the simplest form of all the semiconductor devices - 51MOS: Metal-Oxide-Semiconductor
- 52Neutral Gate
- 53Positive Gate, P-type Substrate
- 54Gap in a Wire
- 55N-Channel Pass Transistor (or MOSFET)
- 56Open N-Channel
- 57Closed N-Channel
- 58N-Channel Pass Transistor: a Controllable Switch
- 59P-Channel Pass Transistor
- 60CMOS: Complementary MOS• A circuit that contains both P-channel and N-channel devices is called CMOS
• Notice that we need…
– A positive voltage (to control the N-channel transistors)
– A negative voltage (to control the P-channel transistors)
• So voltages are not going to be 0V and 5V but 2.5V and -2.5V
• CMOS is currently the dominant technology (since 1970s) - 61CMOS Inverter
- 62Implementation of z = nor2 x y
- 63Requirements of a Logic Circuit• For all inputs, the output must be connected to either “1” or “0”
– Otherwise, the output signal is floating (neither “1” nor “0”)
• There must not be any combination of input values that cause both parts of
the circuit to close
– This would connect the +v/2 and -v/2 power supplies together, resulting
in a short circuit! - 64Integrated CircuitsWe can fabricate many transistors on the same chip of silicon
VLSI: Very large-scale integration
– Millions of transistors - 65We can also fabricate wires connecting transistors directly on the chip – Short wiresShort wires can simply be N or P type paths that are surrounded by the
opposite type - 66We can also fabricate wires connecting transistors directly on the chip – Long wiresLong wires are implemented by placing paths of aluminum on top of the
surface - 67Integrated Circuits: Fabrication• A photographic process
– Efficient because all the “devices” on the chip are manufactured in parallel
• The chip is built up in stages
– E.g. doping selected regions to change them from P to N type
• Photoresist is used to mask off the portions that are to be left unchanged - 68Fabricating one layer: doping– Photoresist
– Expose photoresist to patterned light
– Dissolve weakened photoresist
– Expose chip surface to doping agent
– Dissolve all photoresist - 69(1) Side view: P-type silicon
- 70(2) Put on photoresistThe chip is immersed in a liquid chemical called photoresist, which coats the
surface
- 71(3) Expose to light through mask (like a photographic negative)
- 72(4) Immerse chip in a moderate solvent to remove the weakened photoresist
- 73(5) Expose chip to hot gaseous N-type doping agent; some atoms go into the substrate
- 74(6) Use a strong solvent to remove all the photoresist
- 75(7) Result: most of the chip surface is P-type, but a selected region is now N-type
- 76The big picture• There are many Major Steps
– Change selected regions to N-type, put on insulator, put on metal layer, …
• Each Major Step requires a sequence of small steps: photoresist, mask, …
• There may be over 100 steps
• But each step is helping to produce several billion transistors, all at once - 77Refinements• The manufacturing process has continually been refined
– Example: some years ago, the feature size became smaller than the
wavelength of visible light!
– Solution: switch to X-rays rather than visible light
• These refinements are the reason Moore’s Law has held for so long
Information
- Description
- Computer Science Flashcards on Week 10, created by Isaac Gilbert on 15/03/2022.
- Created by
- Isaac Gilbert · Mar 2022
- Updated
- Mar 15, 2022
- Views
- 0
- Rating