Computer Organization and Design
Unit 2: Digital Logic & Hardware Description
Based on slides by , , & C.J. IS 501: Comp. Arch. | Dr. | Hardware Description 1
Copyright By PowCoder代写 加微信 powcoder
This Unit: Digital Logic & Hdw Description
System software
• Transistors & fabrication
• Digital logic basics
• Focus on useful components
• Hardware design methods • Introduction to Verilog
CIS 501: Comp. Arch. | Dr. | Hardware Description 2
• Digital logic
• P&H, Appendix C
• Manufacturing
• P&H, Section 1.7
• Introduction to Logic Synthesis using Verilog HDL, Reese & Thornton
• See webpage for other Verilog HDL resources
CIS 501: Comp. Arch. | Dr. | Hardware Description 3
Motivation: Implementing a Datapath
Register File
Data Memory
Insn memory
• Datapath:performscomputation(registers,ALUs,etc.) • ISA specific: can implement every insn (single-cycle: in one pass!)
• Control:determineswhichcomputationisperformed • Routes data through datapath (which regs, which ALU op)
• Fetch:getinsn,translateopcodeintocontrol
• Fetch ® Decode ® Execute “cycle”
CIS 501: Comp. Arch. | Dr. | Hardware Description 4
Two Types of Components
Register File
Data Memory
Insn memory
• Purelycombinational:statelesscomputation • ALUs, muxes, control
• Arbitrary Boolean functions
• Combinational+sequential:storage • PC, insn/data memories, register file
• Internally contain some combinational components
CIS 501: Comp. Arch. | Dr. | Hardware Description 5
Example LC4 Datapath
CIS 501: Comp. Arch. | Dr. | Hardware Description 6
LC4 Datapath
insn[2:0] insn[11:9]
insn[11:9] 3’b111
insn[11:9] 3’b111
216 by 16 bit
r1sel r2sel r1data
216 by 16 bit
Branch Logic
CIS 501: Comp. Arch. | Dr. | Hardware Description
Transistors & Fabrication
CIS 501: Comp. Arch. | Dr. | Hardware Description 8
CIS 501: Comp. Arch. | Dr. | Hardware Description
Intel Pentium M Wafer
Semiconductor Technology
• Basic technology element: MOSFET
• Solid-state component acts like electrical switch • MOS: metal-oxide-semiconductor
• Conductor, insulator, semi-conductor • FET:field-effecttransistor
• 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 (μm), 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 10
Transistors and Wires
CIS 501: Comp. Arch. | Dr. | Hardware Description 11
From slides © ́, MIT
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
power (1) p-transistor
output (“node”)
n-transistor ground (0)
• Complementary n-/p- networks form boolean logic (i.e., gates) • And some non-gate elements too (important example: RAMs)
CIS 501: Comp. Arch. | Dr. | Hardware Description 12
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) • Input=1
• P-transistor open, n-transistor closed • Output discharges to ground (0)
CIS 501: Comp. Arch. | Dr. | Hardware Description 13
Another CMOS Gate Example
• What is this? Look at truth table • 0,0®1
• Result: NAND (NOT AND) • NAND is “universal”
• What function is this?
CIS 501: Comp. Arch. | Dr. | Hardware Description
Digital Building Blocks: Logic Gates
• Logicgates:implementBooleanfunctions • Basic gates: NOT, NAND, NOR
• Underlying CMOS transistors are naturally inverting ( = NOT)
NOT (Inverter) NAND
• NAND, NOR are “Boolean complete”
AB A A AB AB AB
( A | B ) ’
A B ’ | A ’ B
CIS 501: Comp. Arch. | Dr. | Hardware Description
Digital Logic Review
CIS 501: Comp. Arch. | Dr. | Hardware Description 16
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 0,0,0 ® 0 0,0,1 ® 0 0,1,0 ® 0 0,1,1 ® 0 1,0,0 ® 0 1,0,1 ® 1 1,1,0 ® 1 1,1,1 ® 1
• Example above: Out = AB’C | ABC’ | ABC
CIS 501: Comp. Arch. | Dr. | Hardware Description 17
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(programmablelogicarray) • Flexible circuit for doing this
CIS 501: Comp. Arch. | Dr. | Hardware Description 18
PLA Example
• PLA with 3 inputs, 2 outputs, and 4 product terms • Out0=AB’C | ABC’ | ABC
Permanent connections
Programmable connections (unconnected)
CIS 501: Comp. Arch. | Dr. | Hardware Description
Boolean Algebra
• BooleanAlgebra:rulesforrewritingBooleanfunctions • 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 20
Logic Minimization
• Logicminimization
• Iterative application of rules to reduce function to simplest form • Designtoolsdothisautomatically
Out = AB’C | ABC’ | ABC Out = A(B’C | BC’ | BC) Out = A(B’C | (BC’ | BC)) Out = A(B’C | B(C’ | C)) Out = A(B’C | B1)
Out = A(B’C | B)
Out = A((B’ | B)(C | B)) Out = A(1(B | C))
Out = A(B | C)
// distributivity
// associativity
// distributivity (on B)
// tautology // 0/1
// distributivity (on | B) // tautology
CIS 501: Comp. Arch. | Dr. | Hardware Description 21
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
• Examples
• Multiplexer • Adder
CIS 501: Comp. Arch. | Dr. | Hardware Description 22
Multiplexer (Mux)
• Multiplexer(mux):selectsoutputfromNinputs
• 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)
S (1-hot) A
S (binary)
CIS 501: Comp. Arch. | Dr. | Hardware Description
• Adder:adds/subtractstwobinaryintegersintwo’s complement format
• Halfadder:addstwo1-bit“integers”,nocarry-in
• Fulladder:addsthree1-bit“integers”,includescarry-in
• Ripple-carryadder:Nchainedfulladdersadd2N-bitintegers • Tosubtract:negateBinput,setbit0carry-into1
CIS 501: Comp. Arch. | Dr. | Hardware Description 24
Full Adder
• What is the logic for a full adder? • Look at truth table
CI A B 0 00 0 0 1 0 10 0 11 1 00 1 01 1 10 1 11
® C0 S ® 00 ® 0 1 ® 0 1 ® 10 ® 01 ® 10 ® 1 0 ® 1 1
• S=C’A’B |
• CO=C’AB | CA’B | CAB’ | CAB=CA | CB | AB
C’AB’ | CA’B’ | CAB=C^A^B
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 27
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,
CIS 501: Comp. Arch. | Dr. | Hardware Description 28
• 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.
Configurable Logic Blocks (CLBs)
Programmable Interconnect
CIS 501: Comp. Arch. | Dr. | Hardware Description 29
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 30
Configuring FPGAs
• By configuring the CLBs and the interconnect the FPGA can be ‘programmed’ to implement the desired operation.
Configurable Logic Blocks (CLBs)
Programmable Interconnect
CIS 501: Comp. Arch. | Dr. | Hardware Description 31
Hardware Design Methods
CIS 501: Comp. Arch. | Dr. | Hardware Description 32
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
CIS 501: Comp. Arch. | Dr. | Hardware Description 33
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 34
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 35
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]);
CIS 501: Comp. Arch. | Dr. | Hardware Description
Verilog HDL
• Verilog:HDLwewillbeusing
• 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;
These aren’t variables These aren’t function calls
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]);
CIS 501: Comp. Arch. | Dr. | Hardware Description 38
HDLs are not “SDLs”
• SDL == Software Description Language (e.g., Java, C)
• Similar in some (intentional) ways … • Syntax
• 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 39
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
• Softwareissequential
• 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
CIS 501: Comp. Arch. | Dr. | Hardware Description 40
HDL: Behavioral Constructs
• HDLs have low-level structural constructs
• Specify hardware structures directly
• Transistors,gates(and,not)andwires,hierarchyviamodules
• 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,forloops
• 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 41
HDL: Simulation
• Another use of HDL: simulating & testing a hardware design • Cheaper & faster turnaround (no need to fabricate)
• More visibility into design (“debugger” interface)
• HDLshavefeaturesjustforsimulation
• 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
CIS 501: Comp. Arch. | Dr. | Hardware Description 42
FPGA “Design Flow”
HDL source code
implementation (place & route)
netlist (wires, gates, FFs)
• 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 43
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 44
Verilog HDL
CIS 501: Comp. Arch. | Dr. | Hardware Description 45
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
CIS 501: Comp. Arch. | Dr. | Hardware Description 46
Modern HDLs
• BlueSpec
• MIT startup from 2003
• more functional style, richer types • inspired by Haskell
• from Berkeley in 2012 • embedded DSL in IS 501: Comp. Arch. | Dr. | Hardware Description 47
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 48
Our Verilog HDL
• We’regoingtolearnafocusedsubsetofVerilog • 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 49
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 50
(Gate-Level) Structural Verilog
• Primitive“datatype”:wire • Have to declare it
Structural
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);
CIS 501: Comp. Arch. | Dr. | Hardware Description
(Gate-Level) Structural Verilog
• Primitive “operators”: gates
• Specifically:and,or,xor,nand,nor,xnor,not,buf
• Can be multi-input: e.g.,or (C, A, B, D) (C= A | B | D) • “Operator”bufjustrepeatsinputsignal(mayamplifyit)
Structural
module mux2to1(input wire S,
input wire A,
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com