程序代做 CSE 371 Computer Organization and Design

CSE 371 Computer Organization and Design

CIS 501: Comp. Arch. | Dr. | Hardware Description
Computer Organization and Design

Unit 2: Digital Logic & Hardware Description

Based on slides by , ,
& C.J. IS 501: Comp. Arch. | Dr. | Hardware Description
This Unit: Digital Logic & Hdw Description
Transistors & fabrication
Digital logic basics
Focus on useful components
Hardware design methods
Introduction to Verilog

System software

credential:
bring a computer

This can be an hidden slide. I just want to use this to do my own planning.
I have rearranged Culler’s lecture slides slightly and add more slides. This covers everything he covers in his first lecture (and more) but may
We will save the fun part, “ Levels of Organization,” at the end (so student can stay awake): I will show the internal stricture of the SS10/20.

Notes to Patterson: You may want to edit the slides in your section or add extra slides to taylor your needs.

CIS 501: Comp. Arch. | Dr. | Hardware Description

Digital logic
P&H, Appendix C

Manufacturing
P&H, Section 1.7

Introduction to Logic Synthesis using Verilog HDL, Reese & webpage for other Verilog HDL resources

CIS 501: Comp. Arch. | Dr. | Hardware Description

Motivation: Implementing a : performs computation (registers, ALUs, etc.)
ISA specific: can implement every insn (single-cycle: in one pass!)
Control: determines which computation is performed
Routes data through datapath (which regs, which ALU op)
Fetch: get insn, translate opcode into control
Fetch  Decode  Execute “cycle”

CIS 501: Comp. Arch. | Dr. | Hardware Description

Two Types of Components
Purely combinational: stateless computation
ALUs, muxes, control
Arbitrary Boolean functions
Combinational+sequential: storage
PC, insn/data memories, register file
Internally contain some combinational components

Example LC4 Datapath

CIS 501: Comp. Arch. | Dr. | Hardware Description

insn[11:9]

LC4 Datapath

insn[11:9]

216 by 16 bit

CIS 501: Comp. Arch. | Dr. | Hardware Description

Transistors & Fabrication

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Semiconductor Technology
Basic technology element: MOSFET
Solid-state component acts like electrical switch
MOS: metal-oxide-semiconductor
Conductor, insulator, semi-conductor
FET: field-effect transistor
Channel conducts sourcedrain only when voltage applied to gate
Channel length: characteristic parameter (short  fast)
Aka “feature size” or “technology”
Currently: 0.007 micron (mm), 7 nanometers (nm)
Continued miniaturization (scaling) known as “Moore’s Law”
Won’t last forever, physical limits approaching (or are they?)

CIS 501: Comp. Arch. | Dr. | Hardware Description
Transistors and Wires

From slides © ć, MIT

CIS 501: Comp. Arch. | Dr. | Hardware Description
Complementary MOS (CMOS)
Voltages as values
Power (VDD) = “1”, Ground = “0”
Two kinds of MOSFETs
N-transistors
Conduct when gate voltage is 1
Good at passing 0s
P-transistors
Conduct when gate voltage is 0
Good at passing 1s
Complementary n-/p- networks form boolean logic (i.e., gates)
And some non-gate elements too (important example: RAMs)

ground (0)
n-transistor
p-transistor

CIS 501: Comp. Arch. | Dr. | Hardware Description
Basic CMOS Logic Gate
Inverter: NOT gate
One p-transistor, one n-transistor
Basic operation
P-transistor closed, n-transistor open
Power charges output (1)
P-transistor open, n-transistor closed
Output discharges to ground (0)

CIS 501: Comp. Arch. | Dr. | Hardware Description
Another CMOS Gate Example
What is this? Look at truth table
Result: NAND (NOT AND)
NAND is “universal”

What function is this?

NOR – Not Or

CIS 501: Comp. Arch. | Dr. | Hardware Description
Digital Building Blocks: Logic Gates
Logic gates: implement Boolean functions
Basic gates: NOT, NAND, NOR
Underlying CMOS transistors are naturally inverting ( = NOT)

NAND, NOR are “Boolean complete”

NOT (Inverter)

Digital Logic Review

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Boolean Functions and Truth Tables
Any Boolean function can be represented as a truth table
Truth table: point-wise input  output mapping
Function is disjunction of all rows in which “Out” is 1

A,B,C  Out

Example above: Out = AB’C | ABC’ | ABC

We will return to this when we talk about CLBs in FPGAs

CIS 501: Comp. Arch. | Dr. | Hardware Description
Truth Tables and PLAs
Implement Boolean function by implementing its truth table
Takes two levels of logic
Assumes inputs and inverses of inputs are available (usually are)
First level: ANDs (product terms)
Second level: ORs (sums of product terms)

PLA (programmable logic array)
Flexible circuit for doing this

CIS 501: Comp. Arch. | Dr. | Hardware Description
PLA Example
PLA with 3 inputs, 2 outputs, and 4 product terms
Out0 = AB’C | ABC’ | ABC

Permanent connections
Programmable connections (unconnected)

One implementation with a programmable interconnect.

CIS 501: Comp. Arch. | Dr. | Hardware Description
Boolean Algebra
Boolean Algebra: rules for rewriting Boolean functions
Useful for simplifying Boolean functions
Simplifying = reducing gate count, reducing gate “levels”
Rules: similar to logic (0/1 = F/T)
Identity: A1 = A, A | 0 = A
0/1: A0 = 0, A | 1 = 1
Inverses: (A’)’ = A
Idempotency: AA = A, A | A = A
Tautology: AA’ = 0, A | A’ = 1
Commutativity: AB = BA, A | B = B | A
Associativity: A(BC) = (AB)C, A | (B | C) = (A | B) | C
Distributivity: A(B | C) = AB | AC, A | (BC) = (A | B)(A | C)
DeMorgan’s: (AB)’ = A’ | B’, (A | B)’ = A’B’

CIS 501: Comp. Arch. | Dr. | Hardware Description
Logic Minimization
Logic minimization
Iterative application of rules to reduce function to simplest form
Design tools do this automatically

CIS 501: Comp. Arch. | Dr. | Hardware Description
Non-Arbitrary Boolean Functions
PLAs implement Boolean functions point-wise
E.g., represent f(X) = X+5 as [05, 16, 27, 38, …]
Mainly useful for “arbitrary” functions, no compact representation

Many useful Boolean functions are not arbitrary
Have a compact implementation
Multiplexer

CIS 501: Comp. Arch. | Dr. | Hardware Description
Multiplexer (Mux)
Multiplexer (mux): selects output from N inputs
Example: 1-bit 4-to-1 mux
Not shown: N-bit 4-to-1 mux = N 1-bit 4-to-1 muxes + 1 decoder

S (binary)

CIS 501: Comp. Arch. | Dr. | Hardware Description
Adder: adds/subtracts two binary integers in two’s complement format
Half adder: adds two 1-bit “integers”, no carry-in
Full adder: adds three 1-bit “integers”, includes carry-in
Ripple-carry adder: N chained full adders add 2 N-bit integers
To subtract: negate B input, set bit 0 carry-in to 1

CIS 501: Comp. Arch. | Dr. | Hardware Description
Full Adder
What is the logic for a full adder?
Look at truth table

CI A B  C0 S
0 0 0  0 0
0 0 1  0 1
0 1 0  0 1
0 1 1  1 0
1 0 0  0 1
1 0 1  1 0
1 1 0  1 0
1 1 1  1 1

S = C’A’B | C’AB’ | CA’B’ | CAB = C ^ A ^ B
CO = C’AB | CA’B | CAB’ | CAB = CA | CB | AB

CIS 501: Comp. Arch. | Dr. | Hardware Description
N-bit Adder/Subtracter

More later when we cover arithmetic

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Alternative to Fabrication: FPGA
We’ll use FPGAs (Field Programmable Gate Array)
Also called Programmable Logic Devices (PLDs)

An FPGA is a special type of programmable chip
Conceptually, contains a grid of gates
The wiring connecting them can be reconfigured electrically
Using more transistors as switches
Once configured, the FPGA can emulate any digital logic design
Tool converts gate-level design to configuration

Hardware prototyping (what “we” are doing)
Low-volume special-purpose hardware
Network processing. FPGAs in AWS,

A Field Programmable Gate Array contains a collection of configurable logic elements and a programmable interconnect that can be set up to perform the desired logical operations.
CIS 501: Comp. Arch. | Dr. | Hardware Description

Configurable Logic Blocks
Each of the configurable logic blocks (or logic cells) contains some lookup tables and one or more flip-flops.
By setting the entries in the lookup tables (LUTs) these units can be programmed to implement arbitrary logical functions on their inputs.
http://en.wikipedia.org/wiki/Field-programmable_gate_array
ZedBoard has 85K logic cells
CIS 501: Comp. Arch. | Dr. | Hardware Description

walkthrough LUT-as-gate

Configuring FPGAs
By configuring the CLBs and the interconnect the FPGA can be ‘programmed’ to implement the desired operation.
CIS 501: Comp. Arch. | Dr. | Hardware Description

Hardware Design Methods

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Hardware Design Methodologies
Fabricating a chip requires a detailed layout
All transistors & wires
How does a hardware designer describe such design?
(Bad) Option #1: draw all the masks “by hand”
All 1 billion transistors? Umm…
Option #2: use computer-aided design (CAD) tools to help
Layout done by engineers with CAD tools or automatically
Design levels – uses abstraction
Transistor-level design – designer specifies transistors (not layout)
Gate-level design – designer specifics gates, wires (not transistors)
Higher-level design – designer uses higher-level building blocks
Adders, memories, etc.
Or logic in terms of and/or/not, and tools translates into gates

Describing Hardware
Two general options

Schematics
Pictures of gates & wires

Hardware description languages
Use textual descriptions to specify hardware

Translation process called “synthesis”
Textual description -> gates -> full layout
Tries to minimizes the delay and/or number of gates
Much like process of compilation of software
Much slower!

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Schematics
Draw pictures
Use a schematic entry program to draw wires, logic blocks, gates
Support hierarchical design (arbitrary nesting)
Good match for hardware which is inherently spatial
Time consuming, “non-scalable” (large designs are unreadable)
Rarely used in practice (“real-world” designs are too big)

CIS 501: Comp. Arch. | Dr. | Hardware Description
Hardware Description Languages (HDLs)
Write “code” to describe hardware
HDL vs. SDL
Specify wires, gates, modules (also hierarchical)
Easier to create, edit, modify, scales well
Misleading “sequential” representation: must still “think” spatially (gets easier with practice)
module mux2to1(S, A, B, Out);
input S, A, B;
output Out;
wire S_, AnS_, BnS;

not (S_, S);
and (AnS_, A, S_);
and (BnS, B, S);
or (Out, AnS_, BnS);

CIS 501: Comp. Arch. | Dr. | Hardware Description
(Hierarchical) HDL Example
Build up more complex modules using simpler modules
Example: 4-bit wide mux from four 1-bit muxes
module mux2to1_4(S, A, B, Out);
input [3:0] A;
input [3:0] B;
output [3:0] Out;

mux2to1 mux0 (S, A[0], B[0], Out[0]);
mux2to1 mux1 (S, A[1], B[1], Out[1]);
mux2to1 mux2 (S, A[2], B[2], Out[2]);
mux2to1 mux3 (S, A[3], B[3], Out[3]);

Key point – abstraction of designs.

CIS 501: Comp. Arch. | Dr. | Hardware Description
Verilog HDL
Verilog: HDL we will be using
Syntactically similar to C (by design)
Ease of syntax hides fact that this isn’t C (or any software lang)
We will use a few lectures to learn Verilog
module mux2to1_4(S, A, B, Out);
input [3:0] A;
input [3:0] B;
output [3:0] Out;

mux2to1 mux0 (S, A[0], B[0], Out[0]);
mux2to1 mux1 (S, A[1], B[1], Out[1]);
mux2to1 mux2 (S, A[2], B[2], Out[2]);
mux2to1 mux3 (S, A[3], B[3], Out[3]);
These aren’t variables
These aren’t function calls

CIS 501: Comp. Arch. | Dr. | Hardware Description
HDLs are not “SDLs”
SDL == Software Description Language (e.g., Java, C)
Similar in some (intentional) ways …
Named entities, constants, scoping, etc.
Tool chain: synthesis tool analogous to compiler
Multiple levels of representation
“Optimization”
Multiple targets (portability)
“Software” engineering
Modular structure and parameterization
Libraries and code repositories
… but different in many others
One of the most difficult conceptual leaps of this course

CIS 501: Comp. Arch. | Dr. | Hardware Description
Hardware is not Software
Just two different beasts (or two parts of the same beast)
Things that make sense in hardware, don’t in software, vice versa
One of the main themes of this course

Software is sequential
Hardware is inherently parallel and “always on”
Have to work to get hardware to not do things in parallel
Software atoms are purely functional (“digital”)
Hardware atoms have quantitative (“analog”) properties too
Including correctness properties!
Software mostly about quality (“functionality”)
Hardware mostly about quantity: performance, area, power, etc.

One reason that HDLs are not SDLs

Tip write Verilog but think in terms of schematics.

CIS 501: Comp. Arch. | Dr. | Hardware Description
HDL: Behavioral Constructs
HDLs have low-level structural constructs
Specify hardware structures directly
Transistors, gates (and, not) and wires, hierarchy via modules
Also have mid-level behavioral constructs
Specify operations, not hardware to perform them
Low-to-medium-level: &, ~, +, *
Also higher-level behavioral constructs
High-level: if-then-else, for loops
Some of these are synthesizable (some are not)
Tools try to guess what you want, often highly inefficient
Higher-level  more difficult to know what it will synthesize to!
HDLs are both high- and low-level languages in one!
And the boundary is not clear!

CIS 501: Comp. Arch. | Dr. | Hardware Description
HDL: Simulation
Another use of HDL: simulating & testing a hardware design
Cheaper & faster turnaround (no need to fabricate)
More visibility into design (“debugger” interface)

HDLs have features just for simulation
Higher level data types: integers, FP-numbers, timestamps
Routines for I/O: error messages, file operations
Obviously, these cannot be synthesized into circuits

Also another reason for HDL/SDL confusion
HDLs have “SDL” features for simulation

Verilog actually designed to support simulation more than synthesis – idea was you would come up with a design and then in the same language write code for testing the design hence a lot of constructs for doing looping and input output that are not related to hardware layout cannot be synthesized.

FPGA “Design Flow”
Hardware compilers are generally much slower than their software counterparts
solving hard problems: many more choices, optimizing for area, power, picosecond-level timing
CIS 501: Comp. Arch. | Dr. | Hardware Description
HDL source code
(wires, gates, FFs)
implementation
(place & route)
simulation

Side note: High-Level Synthesis
Translate “C to gates”
write hardware at a higher level of abstraction than conventional HDLs
greater programmer productivity
need to write stylized C that will synthesize well
tools are still slow
take ESE 532 to learn (much!) more
CIS 501: Comp. Arch. | Dr. | Hardware Description

Verilog HDL

CIS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
HDL History
First HDLs
Late 1970s: VHDL
VHDL = VHSIC HDL = Very High Speed Integrated Circuit HDL
VHDL inspired by programming languages of the day (Ada)
Verilog first introduced
Verilog inspired by the C programming language
VHDL standardized
Verilog standardized (Verilog-1995 standard)
Continued evolution (Verilog-2001 standard)
Both VHDL and Verilog are evolving, still in use today

Modern HDLs
MIT startup from 2003
more functional style, richer types
inspired by
from Berkeley in 2012
embedded DSL in IS 501: Comp. Arch. | Dr. | Hardware Description

CIS 501: Comp. Arch. | Dr. | Hardware Description
Verilog HDL
Verilog is a (surprisingly) big language
Structural constructs at both gate and transistor level
Facilities for specifying memories
Precise timing specification and simulation
Lots of “behavioral” constructs
C-style procedural variables, including arrays
A pre-processor
VPI: Verilog programming interface

CIS 501: Comp. Arch. | Dr. | Hardware Description
Our Verilog HDL
We’re going to learn a focused subset of Verilog
Focus on synthesizable constructs
Focus on avoiding subtle synthesis errors
Use as an educational tool
For synthesis
Structural constructs at gate-level only
A few behavioral constructs
Some testing and debugging features
Rule 1: if you haven’t seen it in lecture, you can’t use it!
Rule 1a: when in doubt, ask!

CIS 501: Comp. Arch. | Dr. | Hardware Description
Basic Verilog Syntax
Have already seen basic syntax, looks like C
C/C++/Java style comments
Names are case sensitive, and can use _ (underscore)
Avoid: clock, clk, power, pwr, ground, gnd, vdd, vcc, init, reset, rst
Some of these are “special” and will silently cause errors

/* this is a module */
module mux2to1(input wire S, input wire A,
input wire B,
output wire Out);
wire S_, AnS_, BnS;
// these are gates
not (S_, S);
and (AnS_, A, S_);
and (BnS, B, S);
or (Out, AnS_, BnS);

CIS 501: Comp. Arch. | Dr. | Hardware Description
(Gate-Level) Structural Verilog
module mux2to1(input wire S, input wire A,
input wire B,
output wire Out);
wire S_, AnS_, BnS;
not (S_, S);
and (AnS_, A, S_);
and (BnS, B, S);
or (Out, AnS_, BnS);

Primitive “data type”: wire
Have to declare it

Structural

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts