Lecture 5:Machine LanguageCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Recap• Using logic gates, we know how to do a bunch of things with bits:- test equality- if-then-else gate- select one bit from a set (universal gate)What Can We Do?• Lots: Any function of bits, we can specify with logic gates.• But, creating dedicated circuitry for every new problem is daunting and inefficient.• Would like a way of using a fixed set of circuits to act like any circuitry we might want.• We can use the state-machine idea to trade gates for time...Concrete Example: Adding• We want to compute the sum of x and y (2-bit numbers). z (3 bits) is the answer and c (2 bits) is the carry.• z0 = (x0 and not y0) or (not x0 and y0)• c0 = (x0 and y0)10011+ 10101c1c0c0x1x0+y1y0z2z1z0Concrete Example: Adding• z1 = (x1 and not y1 and not c0) or (not x1 and y1 and not c0) or (not x1 and not y1 and c0) or (x1 and y1 and c0)• c1 = z2 = (x1 and y1 and not c0) or (x1 and not y1 and c0) or (not x1 and y1 and c0) or (x1 and y1 and c0)10011+ 10101c1c0c0x1x0+y1y0z2z1z0Adding Bytes• Computing zi and ci from xi, yi, and ci-1 can be carried out with 6 ands, 3 ors, 4 nots.• The previous slide uses 16 ands, 6 ors, and 9 nots (not as good).• This operation is called a “full adder”.• By chaining together one full adder per bit, we can make a circuit that adds any number of bits (4, 8, 16, 32, 64, etc.).Hardware• So, any function we want to implement from bits to bits can be carried out by constructing the right circuit of and/or/nots.• Creating a circuit solves the problem “in hardware”.• The advantage of hardware solutions are that they are fast.• The disadvantage is that they are inflexible.Software• The lovely thing about a computer is that the hardware does not have to change for the computer to change its behavior.• A fixed set of circuits can actually change its behavior to represent any desired function!• Build one, reprogram into anything.• Disadvantage of the software approach: Can be much slower.Programming an AdderCircuit level:Instruction level:• H = A xor B = (A and not B) or (not A and B)• C1 = (A and B) or (C and H)• S = H xor C = (H and not C) or (not H and C)xorxorSimple Statements• Still too many different statements.• Break complex statements down into a set of simple statements.• Instead of E = (H and not C) or (not H and C):• acc = not C• acc = acc and H• P = acc• acc = not H• acc = acc and C• acc = acc or P• E = accInstruction Set: 7 Bits• V in 0000...1111 (variables A- P)• 000V: acc = acc and V• 001V: acc = acc or V• 010V: acc = V• 011V: acc = not V• acc: special temporary variable• 100V: V = acc and V• 101V: V = acc or V• 110V: V = acc• 111V: V = not acc0000 A0001 B0010 C0011 D0100 E0101 F0110 G0111 H1000 I1001 J1010 K1011 L1100 M1101 N1110 O1111 PMemory• Need a place to store the various quantities we’re working with.• Main memory is like a giant filing cabinet, where each drawer is numbered consecutively and can store one value.• Need to be able to store and retrieve values.Memory Circuitaddressmem[0] ... mem[21] ... mem[31]Content of mem[21] if address = 21 (010101)Otherwise, FFFFFFFF[T, F, T, F, T]EQUAL5IFTHENELSE7[F, F, F, F, F, F, F]Similar circuits for the other 63 locations.64-loc-inputbitwise ORContent of mem[address] • We’ll have 32 memory locations, for instructions.• Each one has an 5-bit name (0-31) called its “address”.• Memory circuit takes the contents of memory (32 x 7 bits) and an address, 229 bits in all, & outputs the data stored at the corresponding address.Memory Lookupdef memlookup(add, mem): mem00 = mem[0] mem01 = ifthenelse7(equal5(intToByte( 1),add), mem[ 1], mem00) mem02 = ifthenelse7(equal5(intToByte( 2),add), mem[ 2], mem01) mem03 = ifthenelse7(equal5(intToByte( 3),add), mem[ 3], mem02) mem04 = ifthenelse7(equal5(intToByte( 4),add), mem[ 4], mem03) mem05 = ifthenelse7(equal5(intToByte( 5),add), mem[ 5], mem04) mem06 = ifthenelse7(equal5(intToByte( 6),add), mem[ 6], mem05) mem07 = ifthenelse7(equal5(intToByte( 7),add), mem[ 7], mem06) mem08 = ifthenelse7(equal5(intToByte( 8),add), mem[ 8], mem07) mem09 = ifthenelse7(equal5(intToByte( 9),add), mem[ 9], mem08) mem10 = ifthenelse7(equal5(intToByte(10),add), mem[10], mem09) mem11 = ifthenelse7(equal5(intToByte(11),add), mem[11], mem10) mem12 = ifthenelse7(equal5(intToByte(12),add), mem[12], mem11) mem13 = ifthenelse7(equal5(intToByte(13),add), mem[13], mem12) mem14 = ifthenelse7(equal5(intToByte(14),add), mem[14], mem13) mem15 = ifthenelse7(equal5(intToByte(15),add), mem[15], mem14) mem16 = ifthenelse7(equal5(intToByte(16),add), mem[16], mem15) mem17 = ifthenelse7(equal5(intToByte(17),add), mem[17], mem16) mem18 = ifthenelse7(equal5(intToByte(18),add), mem[18], mem17) mem19 = ifthenelse7(equal5(intToByte(19),add), mem[19], mem18) mem20 = ifthenelse7(equal5(intToByte(20),add), mem[20], mem19) mem21 = ifthenelse7(equal5(intToByte(21),add), mem[21], mem20) mem22 = ifthenelse7(equal5(intToByte(22),add), mem[22], mem21) mem23 = ifthenelse7(equal5(intToByte(23),add), mem[23], mem22) mem24 = ifthenelse7(equal5(intToByte(24),add), mem[24], mem23) mem25 = ifthenelse7(equal5(intToByte(25),add), mem[25], mem24) mem26 = ifthenelse7(equal5(intToByte(26),add), mem[26], mem25) mem27 = ifthenelse7(equal5(intToByte(27),add), mem[27], mem26) mem28 = ifthenelse7(equal5(intToByte(28),add), mem[28], mem27) mem29 = ifthenelse7(equal5(intToByte(29),add), mem[29], mem28) mem30 = ifthenelse7(equal5(intToByte(30),add), mem[30], mem29) mem31 = ifthenelse7(equal5(intToByte(31),add), mem[31], mem30)return mem31Writing to Memoryaddressmem[0] ... mem[21] ... mem[31]Content of newval if address = 21 (10101)Otherwise, mem[21] (no change)[T, F, T, F, T]Equal5Ifthenelse7Similar circuits for the other 31 locations.newvalmem[0] ... mem[21] ... mem[31]• Similar circuit allows memory cells to be altered.• mem[address] = newval• If needed for future processing, copied back up at the end of the cycle.Memory Writedef memwrite(active, add, mem, val): return [ ifthenelse7(active and equal5(intToByte( 0),add), val, mem[ 0]),