University of LondonInternational Programmes CO1110 – Introductionto Computing and the Internet Coursework assignment1 2017 – 2018 Sunil BothraSRN: 01305384 Question 1 (a): Convert the positive decimal number17.45 to IEEE 754 single precision representation. Show all of your workingout.The positive, base ten, decimal number 17.45 may be converted to a32-bit single precision IEEE 754 binary floating-point standard representationas follows:A. To convert the integer part, 17, into binary (base 2), the same is dividediteratively by 2, until a quotient equal to zero is arrived at.

The remaindersare tracked for later use.(integer / 2 = quotient + remainder)1) 17 / 2 = 8 + 12) 8 / 2 = 4 + 03) 4 / 2 = 2 + 04) 2 / 2 = 1 + 05) 1 / 2 = 0 + 1B. To construct the base 2 representation of the integer part of the number(17), the remainders are read from the bottom up, as indicated by the bluearrow above. The resulting base 2 representation is obtained17(10) = 1 0001(2)C.

To convert the fractional part (0.45) into binary (base 2), it needs tobe multiplied iteratively by 2, until a fractional part equal to zero isarrived at. The integer part of each step is tracked for later use.(fractional part x 2 = integer + fractional remainder)1) 0.45 × 2 = 0 + 0.92) 0.9 × 2 = 1 + 0.

83) 0.8 × 2 = 1 + 0.64) 0.6× 2 = 1 + 0.25) 0.2 × 2 = 0 + 0.46) 0.

4 × 2 = 0 + 0.87) 0.8 × 2 = 1 + 0.68) 0.6× 2 = 1 + 0.29) 0.2 × 2 = 0 + 0.410) 0.

4 × 2 = 0 + 0.811) 0.8 × 2 = 1 + 0.612) 0.

6 × 2 = 1 + 0.213) 0.2 × 2 = 0 + 0.414) 0.4 × 2 = 0 + 0.

815) 0.8 × 2 = 1 + 0.616) 0.6 × 2 = 1 + 0.217) 0.2 × 2 = 0 + 0.418) 0.4 × 2 = 0 + 0.

819) 0.8 × 2 = 1 + 0.620) 0.6 × 2 = 1 + 0.221) 0.2 × 2 = 0 + 0.422) 0.

4 × 2 = 0 + 0.823) 0.8 × 2 = 1 + 0.624) 0.6 × 2 = 1 + 0.2D.

The blue arrows above indicate the direction in which the integers needsto be read in order to construct a base 2 representation of the originalfraction (0.45). Steps 4 through 23 represent an infinitely recurring loop asstep 8 is identical to step 4. Despite the numerous iterations, no fractionalparts equal to zero were arrived at. However, the number of iterationsperformed above exceed the Mantissa limit (23) and at least one integer thatwas different from zero was found. To construct the base 2 representation ofthe fractional part of the number (0.45), the remainders are read from the topdown, as indicated by the blue arrows above. The resulting base 2representation is obtained (the overlined portion “1001” recurs infinitely)0.

45(10) = 0.011 (2)or0.45(10) = 0.0111 0011 00110011 0011 0011(2)E. By combining the binary representations obtained in steps B and D above,the full binary representation of 17.45, before normalization, is17.45(10) = 1 0001.

011 (2)F. The above binary representation can be normalized by shifting thedecimal 4 places to the left, thus leaving only one non-zero digit to the leftof the same17.45(10) = 1 0001.011 (2) = 1 0001.011 (2) × 20 = 10001.011 (2) × 24G.

Based on steps A through F, the following are the elements needed for a IEEE754 single precision representation:1) Sign: 0 (since the number in question is positive).2) Exponent (unadjusted): 4 (derived from 24 from step F above).3) Mantissa (not normalized): 1.0001 0111 0011 0011 0011 0011 0011 (step F).

These will befed into the following single precision (32-bit) form (Bias = 127) Sign (1) Exponent (8) Fraction (23) H. To convert the unadjusted exponent (4) into binary representation, it isfirst adjusted using the 8-bit bias notation and the result is converted fromdecimal (base 10) to 8 bit binary format, by iteratively dividing by 2 as instep A above.1) Exponent (adjusted) = Exponent (unadjusted) + (2(8-1) – 1) = 4+ (2(8-1) – 1) = (4 + 127)(10) =131(10)2) Dividing iteratively by 2 as shown in step A above1) 131 / 2 = 65 + 12) 65 / 2 = 32 + 13) 32 / 2 = 16 + 04) 16 / 2 = 8 + 05) 8 / 2 = 4 + 06) 4 / 2 = 2 + 07) 2 / 2 = 1 + 08) 1 / 2 = 0 + 13) Reading from the bottom up, the binary representation of adjustedexponent is131(10) = 1000 0011(2)I. To normalise the mantissa, the leading bit (leftmost, given that it isalways 1) and the decimal point (if available), are removed, and the length isadjusted to 23 bits by removing the extra bits from the right Mantissa (normalized) = 1.000 1011 1001 1001 1001 1001 1001 = 0001011 1001 1001 1001 1001J. Based on thecalculations made in steps A through I, the positive decimal number 17.45 canbe converted to IEEE 754 single precision representation as shown belowSign (1 bit) Exponent (8 bits) Mantissa (23 bits) 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 or 17.45(10)= 0 10000011 00010111001100110011001 (32 bits IEEE 754).

Question1 (b): In IEEE 754 single precision, 1.25 isrepresented as: 0 01111111 01000000000000000000000 In IEEE 754 single precision1.26 is represented as: 0 01111111 01000010100011110101110 Explain why thereare many more 1’s in the mantissa of the IEEE 754 representation of 1.26 than1.25.The mantissa is the portion of afloating-point number wherein its significant digits are contained. It isarrived at by converting both the integer as well as the fraction part of agiven number into base 2 representation, adding the results, converting the sum(non-normalized mantissa) to scientific notation and then normalizing the sameby eliminating the leading bit (leftmost, given that it is always 1) and the decimal point (ifavailable), and adjusting the length to 23 bits by removing the extra bits fromthe right (if in excess of 23) or adding the necessary number of zeros (if lessthan 23). The following steps are used to derive the mantissas in IEEE 754single precision for 1.

25 and 1.26:A. The integer part of both numbers is the same (1) so the base 2representation of it is1) 1 / 2 = 0 + 12) 1(10) = 1(2)B. The base 2 representation of the fractional part .

25 of the first numberis1) 0.25 × 2 = 0 + 0.52) 0.5 × 2 = 1 + 0 (Last multiplication step as fractional part equal to 0found)3) 0.

25(10) = 0.0100 00000000 0000 0000 000(2) (Extra 0s added, in blue)C. The base 2 representation of the fractional part .26 of the first numberis1) 0.26 × 2 = 0 + 0.522) 0.

52 × 2 = 1 + 0.043) 0.04 × 2 = 0 + 0.084) 0.08 × 2 = 0+ 0.165) 0.16 × 2 = 0 + 0.326) 0.

32 × 2 = 0 + 0.647) 0.64 × 2 = 1 + 0.288) 0.28 × 2 = 0 + 0.569) 0.

56 × 2 = 1 + 0.1210) 0.12 × 2 = 0 + 0.2411) 0.24 × 2 = 0 + 0.4812) 0.

48 × 2 = 0 + 0.9613) 0.96 × 2 = 1 + 0.9214) 0.92 × 2 = 1 + 0.

8415) 0.84 × 2 = 1 + 0.6816) 0.68 × 2 = 1 + 0.

3617) 0.36 × 2 = 0 + 0.7218) 0.

72 × 2 = 1 + 0.4419) 0.44 × 2 = 0 + 0.8820) 0.88 × 2 = 1 + 0.7621) 0.

76 × 2 = 1 + 0.5222) 0.52 × 2 = 1 + 0.0423) 0.04 × 2 = 0 + 0.0824)0.08 × 2 = 0+ 0.16 0.

26(10) = 0.010 (2) (The overlined part recurs since in steps 4 and 24 the fractional parts repeat).ConclusionSince the integer part of both numbers (1) is the same and both mantissas areprovided, the difference between them is entirely related to the base 2representation of the fractional part, and it can be seen from the resultsobtained in steps B and C that the reason why there are recurring zeros afterthe first two bits of 1.25’s mantissa is due to only two multiplication stepsneeded to arrive at a fractional part that is equal to 0. The rest of 1.

25’smantissa is completed by extra 0s to fill up the 23 bits required. In the case of 1.26’s mantissa, 0.26’s iterative multiplication with 2does not produce a fractional part equal to 0. Each time, during the iteration,there is a residual fraction equal to or larger than 0.5, upon multiplication,there is a remainder of 1, and since an infinitely recurring pattern (Step C4-23) exists, there are many more 1s in the mantissa of an IEEE 754 singleprecision representation of 1.26 than there are in that of 1.25.

0.25(10) = 0.0100 0000 0000 0000 0000 000(2) Mantissa = 0100 0000 0000 0000 0000 000 0.

26(10) = 0.010 (2) Mantissa = 0100 0010 1000 1111 0101 110 Question1 (c): Why is the exponent biased in IEEErepresentation? The IEEE 754 single precisionformat comprises 32 bits as follows:Sign (1 bit) Exponent (8 bits) Mantissa (23 bits) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Within the 8 bits of the exponent the total number of values possibleare as follows:28 = 256If unsigned numbers were to be stored in the exponent they would rangefrom (as shown in the right) 0, 1, 2… 127, 128… 255But, the exponent can be negative or positive. In that case the signedrange that can be contained within the exponent would be as shown on the right.-127, -126, -125… -0, +0, 1, 2… 128 negative numbers positive numbersAs it can been seen from above there are two 0s, one negative, one positive. Soto solve this problem of the extra, redundant 0, the numbers from the signed rangebelow (negative and positive) are mapped to unsigned range above as shown bythe red arrows (as displayed in the two ranges below)0, 1, 2… 127 128, 129… 255The left range maps to all values from -127 to -1 and 0 (128 numbers),the right range maps to all values from 1 to 128 (127 numbers). However, in IEEE754, the minimum exponent of -127 (where every bit is equal to 0) and +128 (all 1s) are reserved for specialvalues such as+- ? (Infinity), denormalized numbers and NaNs (Not aNumber). Hence, the actual exponent range is -126… 127 where -126 is storedas 1 and 0 is stored as 127.

It allows every number from -127 to 127 to beuniquely mapped from 0-254 and avoids mapping the 0 twice. This implies thatthe exponent of 0 is stored with a bias of 127 (0 + 127), the exponent of -126is stored as 1 (-126 + 127), the exponent of 127 is stored as 254 (127 + 127),and so on. Biasing is essential since exponents must be signed values for them torepresent very small as well as very large values. However, two’s complement(how signed values are usually represented) would complicate any comparisons. Thisis why in order to store the exponent in 8 bits, a bias of +127 is added to thebase 10 exponent and then it is converted into a base 2 representation (8-bits)(e.

g., an exponent of 4 is adjusted with a bias of 127 to become 131(10)which is then converted into an 8-bit IEEE 754 single precision representationas 1000 0011(2)). Question2: Considerthe problem of finding the total time to access and read data stored as trackson a computer disk.

This can be described, at its simplest, as access time plustransfer time. Access time is comprised of the average time for the readinghead to find the correct track (known as seek time) plus the rotational delay,or latency. Seek time is zero for fixed-head systems. The rotational latency isthe average time taken for the disc to spin around to the correct place tostart reading. This is considered to be, on average, half the time taken forone complete disk rotation.

The time taken to read data, the transfer time, isgiven by the amount of data on the track to be read, divided by the total dataon the track, all multiplied by the time taken for one disk rotation. Clearlyif all of the data on a track is to be read, then this reduces to the timetaken for one disk rotation. There may, in fact, be delays caused by I/Oqueuing (see Stallings, section Disk Performance Parameters, pages 225-227,tenth global edition), but in the following problem we will just consideraccess time plus transfer time.

Given a moveable-head system with a constantdisk rotation speed of 12,000 revolutions per minute (rpm), an average seektime of 6 milliseconds and 512 byte sectors with 500 sectors per track, answerthe following questions, giving all your working. Give your final answers to(a) and (b) in milliseconds (ms).Question2 (a): The file is sequentially organised, andis stored on 6 complete tracks followed by exactly one half of a track.Data provided:· Disk rotation = 12000 rpm· Avg. Seek time = 6 ms· Sector size = 512 bytes· Sectors / Track = 500· File is sequentiallyand fully distributed across 6.5 tracks.

Formulae used:· Avg. RotationalLatency = = = * Time for one disk rotation (in ms)(Assumption:Minimum latency is 0, based on the disk head being present at the sectorsought. Maximum latency is the equal to one full disk rotation time based onthe disk head just missing the sector sought).· Transfer Time = * Time for one disk rotation (in ms)To calculate: Total time (to access and read data)Total time = AccessTime + Transfer Time(Note: Thecalculations of Avg. Access and Transfer Time below are for reading the first track.

)Avg. Access Time = Avg. Seek Time + Avg. Rotational Latency= 6 ms + * ( * 1000) ms= 6 ms + 0.5 * ms = 6 ms + 2.5 ms= 8.

5msTransfer Time = * Time for one disk rotation (in ms) = * = 5 msTotal Time to read first track = 8.5 + 5 = 13.5 msAssumptions: Since the file is sequentiallyorganised (stored on 6 complete tracks followed by exactly one half of a track)it can be assumed here, that after reading the first track, the other 5.5 trackscan be read without any additional seek time needed, implying that the I/Ooperation, as mentioned in the question, is able to cope with the data flowfrom the disk.

If this is so, only the rotational delay for each subsequent trackneeds to be taken into consideration, viz. – From tracks 2 through6 (full tracks), each track is read in: 2.5+ 5 = 7.

50 ms. – Track 7 (half-full offile data) is read in: =3.75 ms.

Therefore, to readthe full file, distributed across 6.5 sequential tracks, the following totaltime will be required:Total Time to readfirst track = = 13.50 msTotal Time to read tracks 2-6 = 7.5 x 5 = 37.50 msTotal Time to read track 7 = = 03.75 msTotal Time to read 6.5 tracks = = 54.75 ms Question2 (b): The same file as that in part (a) is nowdistributed at random across the disk, i.

e. each sector of the file is randomlyplaced on the disk.Data provided:· Disk rotation = 12,000 rpm· Avg. Seek time = 6 ms· Sector size =512 bytes· Sectors / Track = 500· File’s sectors are randomlydistributed across the disk.Formulae used: Same as answer 2 (a) above.

Assumptions: Since the degree of fragmentation of the fileis unknown, a worst-case scenario is assumed where each sector of the file isin a separate, non-contiguous location, implying that to access the whole file,each single sector will need to be individually accessed (average seek time + averagerotational latency) and then read. Furthermore, as indicated in the question, delayscaused by I/O queuing are not considered for the purposes of this calculation.To calculate: Total time (to access and read data)Total time = Access Time + Transfer TimeTime to read onesector = = = = = 0.01 msAvg. Seek Time = 6.00msAvg.

Rotational latency = 2.00msTotal Time per sector = 8.01ms Total time = No. of sectors to read * Totaltime per sector(to access and read file) = (6.5 tracks * 500sectors) * 8.01 ms = 3,250 * 8.01 ms = 26,032.

5 ms or 26.03seconds Question2 (c): T If the answer to part (a) is X, and the answer to part (b) is Y, expressX as a percentage of Y, giving your answer to one significant figure.X = Timeneeded to access and read data in part (a) = 15.45msY = Timeneeded to access and read data in part (b) = 26,032.50 msX expressed as apercentage of Y = * 100 = 0.

05934889080956496686833765485451 %The first significantfigure of the % = 5In the numericalrepresentation of X expressed as a percentage of Y, the first significant figureis 5, given that the leading zeros are insignificant, but necessary to ensurethe correct positioning of the remaining numbers. In the aforementioned number,the figure to the right of 5, is 9, and since this is greater than 5, it isrounded up as shown below:X as a % of Y to onesignificant figure = 0.06 %1 Question3 (a): Explain what is meant by Locality ofreference and how this is exploited in cache memory to improve performance. Youranswer should be at most two paragraphs long – a paragraph is considered toconsist of no more than 8 sentences here. Locality of referenceThe tendency of a processor to access the same set of memory locations repetitivelyover a short period of time.154A distinction is made in the literature between spatial locality and temporal locality.Spatial locality refers to the tendency of execution to involve a number of memorylocations that are clustered. This reflects the tendency of a processor to accessinstructions sequentially.

Spatial location also reflects the tendency of aprogram to access data locations sequentially, such as when processing a tableof data. Temporal locality refers to the tendency for a processor to accessmemory locations that have been used recently. For example, when an iterationloop is executed, the processor executes the same set of instructionsrepeatedly. Traditionally, temporal locality is exploited by keeping recentlyused instruction and data values in cache memory and by exploiting a cachehierarchy. Spatial locality is generally exploited by using larger cache blocksand by incorporating prefetching mechanisms (fetching items of anticipated use)into the cache control logic.