Discovering Hamming Codes

July 18th, 2010 admin

Digital data, transmitted over a communication medium (wireless, optical fiber, copper wire), or stored in some storage medium (such as computer memory or hard disk), is prone to bit-flips and errors. For example, if the message “10110101000101010″ means “BILL JOHN” and communication channel noise flips a bit, the message received may be “10010101000101010″, meaning, “KILL JOHN”. Now, that could create a problem. The problem also exists in data that is sitting untouched on a digital storage medium. Have you ever noticed that if you open some photo file on your computer, after years of storage, they develop strange colors and often do not display fully? This could be due to some bit errors in the stored 1s and 0s that represent the image file data. Read the rest of this entry »

Posted in Information, Tidbits, Tutorials, Uncategorized | No Comments »

Thoughts on the mathematical constant e

May 16th, 2010 admin

e for exponential

The mathematical constant shows up in strange places. Moreover, its significance is not as easy to grasp as that of the other famous constant, , because there is no easy physical object in whose context to imagine it. For example, is the ratio of the circumference to the diameter of a circle. Yes, it is irrational, but if you can get over that mystery (or ignore it for the time being), it is straightforward to imagine what is. Every circle does seem to have a certain circleness, which makes them all look the same. It is intuitively not hard to agree with the hunch that every circle has an unchanging ratio between the circumference and the diameter; and it makes sense to keep that ratio handy and give it a name.

The constant is considerably more elusive. It appears, at first, to be a number you would not go hunting after. You just happen to stumble upon in during one of your mathematical excursions; it seems interesting enough that you then pick it up and put in in your pocket for some potential use later. After stumbling upon the same thing along other mathematical excursions, in hindsight, it does seem to be something rather useful. Something you should have gone looking for. Read the rest of this entry »

Posted in Information, Tidbits, Tutorials | No Comments »

We made a garden trellis with PVC piping

May 2nd, 2010 admin

Figure1: Basic plan showing the material required

We have two 4′x8′ (4 feet by 8 feet) raised beds, which we use for vegetable plants. Kavita has been asking me to either buy or build a trellis for her climbing plants (cucumbers, tomatoes and eventually some types of squash and gourds). I read several websites online and decided to build a simple trellis using PVC piping. It took one trip to the local Home Depot, and then about 2 hours of work. The cost for the material was under $10 (I already had all the tools needed).

We decided to build one and test it out before getting carried away and building more. We decided that we would roughly want the trellis to be 4 feet wide by 5 feet high. At the Home Depot we did some quick calculations based on the basic design we had in mind and came up with a total of about 29 feet of PVC tube. The calculation is shown in Figure 1.

Figure 2: Materials and Tools for the project (4-way, + shaped, PVC connector missing)

The PVC pipes are sold in 10′ pieces. We got 3 pieces. We also got some string (I tried polypropylene string since I did not know any better, we’ll see how that works out).

Figure 2 shows most of the material and tools. The one caveat is, since I took this picture after completing the project, the one 4-way 1/2″ PVC pipe connector used at the center of the frame is missing from the picture. I had extra connectors of the other type, so I could use them for the picture. Also, one other thing that is missing from the picture is a power drill and drill bits. I used a 3/16″ drill bit to drill evenly spaced holes in the pipes to draw the string through, to create a framework.

Figure 3: Trellis plan with the stringing shown

Figure 4: Framework ready, stringing is yet to be completed

The spacing between the holes and how the trellis is supposed to look eventually is shown in Figure 3.

The thing that took the most time was measuring and marking the PVC pipes, cutting them to the right size with the saw, then measuring and marking the locations for the holes for the string to go through and then drilling the holes with the power drill. Since the PVC pipe keeps rolling about, making it stable before drilling is important. I just used an old rag to wrap around the pipe in order to hold it somewhat still.

Once the pieces were all ready, putting the trellis together took less than 10 minutes. There was no need for glue, since the connectors fit quite snugly. Figure 4 shows the trellis laid out on the lawn (with only one piece of string drawn through, Kavita will work on getting the rest of the mesh this evening).

We are not sure how well this will hold up, how long it will last etc. I will update the post with some pictures on the trellis in action, later.

Posted in Experiences, Information, Tutorials | No Comments »

Cool Gate-Level Logic Simulation Tool

November 14th, 2009 admin

Dr. Mark Hill of University of Wisconsin Madison pointed out the existence of this really cool learning aid to his class Logic Design class in October 2009. He also provides some guidelines about how to use the tool. Give it a shot if you like to play around with AND, OR, NOT gates and build logic. You can build “memory” structures too, something that can remember state. The following text is from Dr. Hill’s email. Enjoy. Read the rest of this entry »

Posted in Tidbits, Tutorials | No Comments »

The Mathematics of Mortgage, Overpayment and Refinancing Decisions

October 7th, 2009 admin

With mortgage interest rates at historically low values refinancing home loans is an option currently being investigated by many here in the US. I, too, considered the same issue recently and discovered that this is not an easy decision to make. I developed a spreadsheet to figure out if this was a good idea. You can download this spreadsheet by clicking on this link (Microsoft Excel 2003). In general, the spreadsheet was also intended to show how loan repayment terms are set, how banks make money on loans, when overpaying monthly payments makes sense etc. Feel free to use the spreadsheet and improve upon it or tailor it to your situation. The rest of this article is a tutorial on how to make decisions about mortgages, how mortgages work in general, whether overpayment of the monthly payment makes sense, and what to consider when refinancing. The focus will be on the mathematical aspects of the decision making. Read the rest of this entry »

Posted in Experiences, Information, Tutorials | 4 Comments »

Notes on Memory Consistency and Cache Coherence

June 27th, 2008 admin

Here are some of my notes on the topic of memory consistency and cache coherence, and how uniprocessor and multiprocessor cores have to be built to support the consistency models. Most of this was written up when I was preparing for my Qualifying Exam at NC State University last semester. This is a relatively complicated topic to understand well, and there might still be several mistakes in how I understood the ideas. Also, this might only make sense, and be interesting, to people familiar with these areas of computer architecture. Here’s the pdf file: Notes on Memory Consistency and Cache Coherence

Posted in Information, Tutorials | No Comments »

Setup and Hold Violations in Digital Systems

May 19th, 2008 admin

I wrote this up when trying to prepare for my PhD Qualifying Examination this past semester (Spring 2008). It is a pdf file. You can read it here.

Posted in Tutorials | No Comments »

Finally, one Contact List to rule them all

July 29th, 2007 admin

I have a Yahoo email account. I have a Google email account. I have a few more that I do not use much. Each email application or service provider typically has an Address Book or Contacts List, which we can use to list the names, email addresses and other information about people. For a while, I have been thinking about getting the contact lists organized. There were several layers to the word “organized” and I was apprehensive about starting to peel those layers. The first layer of the problem was figuring out which mail server I wanted to stick to. The next thought was to create a superset of all the contact lists, currently scattered across applications and mail servers, at one place. The next issue was to find a way to update the contact list quickly, rather than clicking around a web-based Address Book or Contact List applications such as the one provided by Yahoo and Google Mail. Then there was the hope that I could keep a copy of the contact list locally on my personal computer, in case, at some point, I did not have internet access to get to the Yahoo Address Book.

This list of requirements seemed formidable in itself, yet, what made me skeptical of a final solution, was one last requirement I had. I had maintained a list of birthdays and anniversaries in a text file separate from the contact lists in the mail servers I mentioned. It was a simple text file and a simple Perl script I wrote could go through this text file everyday and send me an email if it found any upcoming event. I wanted to retain the ability to do such scripting and not have to maintain a separate text file version of the contact list, just for the purposes of being able to run such a reminder script.

After collecting and formulating these thoughts over a long time, I finally spent a few minutes last week looking for a solution to the multi-layered problem. Searching on the internet revealed that there WAS a relatively easy solution that fixes ALL the above problems, including giving me the ability to run a simple script to extract birthday and anniversary information! Here is the solution. Yahoo and Google Address Books allow the existing contacts-list to be exported as a CSV (Comma Separated Variable) file, or a CSV file to be imported to populate the Contact List or Address Book application. A CSV file, as the name suggests, is just a regular text file, with many fields belonging to a record typed across a single line, with the comma symbol (“,”) separating the fields. A new record starts in a new line. The file can be opened with a regular text-editor such as Notepad, Wordpad or Textpad in Windows and vi, pico and emacs in Unix. The file may also be opened using Microsoft Excel spread sheet and the fields show up in separate column and the lines show up in separate rows. This solves the problem of easily modifying the contact list in bulk and storing the contact list as a local file on your personal computer. The CSV file is compatible across Yahoo and Google, and probably across many other applications like Microsoft Outlook and Orkut (web-based networking application). The CSV file can then be imported into Yahoo Mail, Google Mail or other such applications. Problem solved. Single contact list. Storable and updateable locally. Uploadable to multiple web-based servers.

The CSV file based common contact list also allowed me to enter the anniversary and birthday in appropriate columns. I wrote a script called contact.py in the Python scripting language to read the contact list file as a simple text file (in the CSV format) and search for upcoming events. This allowed me to get rid of the earlier text file I had my Perl script read. The CSV file, I called it contactlist.csv, was truly the one file I needed to retain for all my address-book related needs. Whenever I want to add a new contact or update information about an existing contact, I update the local copy of the contact list, contactlist.csv, and then import it into Yahoo Mail and Google Mail to keep them up to date. I have noticed that before I import the latest contactlist.csv file into Yahoo or Google, I need to delete all the existing contacts from Yahoo and Google, respectively. Once, we have an empty contact list on the mail server, the importing of contactlist.csv recreates the complete list. Not starting with an empty contact list on the mail servers, creates duplicates, probably because the “import” function is not smart enough to recognize duplicates.

Here is an example of what a few rows from the CSV file contactlist.csv looks like. It gives us idea of what the fields are. The example also shows that all the fields in a CSV file need not be filled. A field can be left empty if we do not know the information relating to that field for a given contact. Also, I use xxxx for the year field of a date (such as a birthday or an anniversary date), in case I do not know the year. This is OK because the script that parses this CSV file, called contact.py, and which is shown later, does not use the year field to determine if an anniversary is approaching. It only uses the day and month parts of the field.

First,Middle,Last,Nickname,Email,Messenger ID,Home,Work,Pager,Fax,Mobile,Other,Yahoo! Phone,Alternate Email 1,Alternate Email 2,Personal Website,Business Website,Title,Company,Work Address,Work City,Work State,Work ZIP,Work Country,Home Address,Home City,Home State,Home ZIP,Home Country,Birthday,Anniversary,Custom 1,Custom 2,Custom 3,Custom 4,Comments,Messenger ID1,Messenger ID2,Messenger ID3,Messenger ID4,Messenger ID5,Messenger ID6,Messenger ID7,Messenger ID8,Messenger ID9,Skype ID,IRC ID,ICQ ID,Google ID,MSN ID,AIM ID,QQ ID
Shahrukh,Mayur,Khan,srk,srk@bollywood.com,,,,,,,,,,,,,,,,,,,,,,,,,1/2/xxxx,,,,,,,,,,,,,,,,,,,,,,

Here is the contact.py Python script which then works on the CSV file called contactlist.csv with contents as shown above, and sends email to your email account. You might have to appropriately fix some of the fields in the script to get it to work. I present it here just as a hint.

import csv, datetime, re
from string import split
filename = “contactlist.csv”
warnZone = 8 #number of days before which email reminder should be sent

import smtplib
smtpserver = ‘mailserver.department.company.com’
AUTHREQUIRED = 0
RECIPIENTS = ['gol345die@gmail.com']
SENDER = ['con789vey@po.doc.com']
session = smtplib.SMTP(smtpserver)
smtpresult = session.sendmail(SENDER, RECIPIENTS, content)
if smtpresult:
errstr = “”
for recip in smtpresult.keys():
errstr = “”"Could not deliver mail to : %s Server said: %s %s %s”"” % (recip, smtpresult[recip][0], smtpresult[recip][1], errstr)
raise smtplib.SMTPException, errstr

Posted in Information, Tutorials | 2 Comments »

Cycles per Instruction and its components

April 30th, 2006 admin

Cycles per Instruction is one way to evaluate the microarchitecture’s effect on a processor’s performance. Performance also depends on what constitutes a cycle (frequency of the machine) and what constitutes an instruction (the architecture of the machine). Interestingly, the ratio of these two, i.e. Cycles per Instruction, tells us about something other than those two factors. CPI tells us how many cycles, at the given frequency, the machine takes to chomp down instructions of the given architecture. In other words CPI tells us about the microarchitectural robustness of a design. It tells us, given a certain cycle period (frequency) and a certain group of instructions (architecture), how many cycles does it take to execute an “average” instruction. The “average” instruction depends on the workload (the program) being run through the processor. And therefore, when quoting CPI’s the workload to which that CPI applies is also quoted. The smaller the CPI the better performing a computer system is, all other factors such as the frequency and architecture remaining the same. Of course, other factors such as area, complexity and power must be considered, in addition to performance and the definition of “better” changes accordingly.

CPI is affected by several factors. Architects and designers often need to know where to start when trying to improve performance by making microarchtectural changes. The overall CPI has to be broken into components and the component that is contributing the largest is usually attacked first, since improvement in that design component could potentially reduce the CPI by the largest amount. I will come back to this point again with an example, shortly. For this write-up I will break the CPI into two main components. The “core” component and the “memory-nest” component. The core component deals with all the microarchitectural decision within the processing unit, which in modern microprocessors includes several pipelines (superscalar machines), each with several stages and associated logic – instruction fetch, decode, issue, register access, execute, write-back etc. The memory-nest component deals with getting appropriate instructions and data from the memory. Several levels of caching is provided to take advantage of certain properties seen in programs. These properties are spatial-locality (if a certain memory location is used, something nearby will be used soon) and temporal locality (if a certain memory location is used, it will likely be used again). To keep the data close at hand, and to avoid the potentially hundreds of processor cycles worth of time to go to the memory every time a new instruction or data is needed, instructions and data are stored in caches. There are some great resources on the web and in books which talk about caches in more detail. For this write-up it suffices to say that caches usually are arranged in a hierarchy. Level 1 is the smallest cache but is the fastest to access and is called the L1Cache. Level 2 cache is bigger than the Level 1 cache but because it is bigger and is usually only accessed after it it known that the instruction or data the core was looking for was not available in the L1Cache, it is slower. It is called the L2Cache. Usually the hierarchy has 2-3 levels of caching.

Therefore, if the CPI component is mostly affected not by the design of the core itself, but because of the sizes or geometries of the caches, the designers would be better served by the information that the memory-nest, or more accurately, a certain level cache should be the first place to look for potential improvements, rather than the core. This brings us to the two main topics of this article. First, what quantities in the cache must be measured to help understand its effect on the CPI. Secondly, from these statistics collected on the caches, how do we build the overall CPI number.

Cache Statistics – What they are, what they mean

When modeling caches there are 4 statistics that are often talked about. These are all not completely independent, and are, therefore, easy to get confused about. The 4 main performance-realted statistics collected for a cache are:

MissesPerReference
HitsPerReference
MissesPerInstruction
HitsPerInstruction

MissesPerReference indicates the ratio of how many times, of all the times the cache was accessed, was the cache unable to provide the data requested. HitsPerReference is the complement. It is the ratio of how many times, out of all the times the cache was accessed, was the cache able to provide the data requested. The complementary nature of these quantities makes it necessary to only quote one number.

MissesPerReference + HitsPerReference = 1

MissesPerInstruction is not that straightforward. It is the ratio of how many times the accesses to the cache missed, out of all the “instructions in the workload”! This is a strange measure at first, and takes some getting used to. It’s the ratio if a design-dependent variable quantity – cache misses, to an unchanging quantity, the number of instructions in the workload. In the earlier measure of missesPerReference, the denominator, the number of references to the cache, was variable depending on what happened before this cache was reached by the instruction flow. The number of reference to this cache depends on how well the previous levels of cache did. HitsPerInstruction, similarly is the ratio of the number of hits in the cache to the total number of instructions in the workload. MissesPerInstructions and HitsPerInstruction do NOT add up to 1! They add up to the number of references made to the cache per instruction.

These 4 quantities are depicted by an example in Figure1.

Why collect PerInstruction statistics

So the question is, “what is the reason we need these two ways of looking at a cache’s performance?”. Why doesn’t the simpler PerReference style of collecting stats suffice? The answer is that the PerReference numbers are great for designing the cache under study provided the number of references does not change, which implies, the design before the cache in study remains unchanged. The PerInstruction numbers are useful to get an idea of how much the cache under study is contributing to the overall CPI. We will shortly see how that overall CPI is calculated from the PerInstruction numbers. Before the PerReference numbers can be used to improve cache designs, the PerInstruction numbers must point out that it is worthwhile to go after a cache design because the cache is adding a big component to the CPI of the system. And we want to keep the CPI low as far as possible. That is why we want to keep track of the PerInstruction statistics.

How to breakdown overall CPI into components

There are two ways to break the overall CPI, or another way to look at it is, two way to build the overall CPI.
One way is to look at what fraction of instructions “pass through” each level (whether they hit or miss at that level is immaterial) in the hierarchy and add up the cycles they spend at each level. The idea is depicted in Figure 2.
The other way is to look at what fraction of instructions “finish at” each level (i.e. they hit) and add up the cycles those fractions take to finish their journey through the memory hierarchy. The idea is depicted in Figure 3.

Method 1: Breaking CPI into components for each level of the memory hierarchy an instruction passes through

This method is often used to represent a CPI stack, which assigns a portion of the CPI to each level. This is very useful in figuring out which level of the cache to go after for improvements.

CPI = CoreComponent + L1Component + L2Component + L3Component + MemComponent

Here the overall CPI is reached by adding CPI contributions at each level of the memory hierarchy. Simulation models for the core often generate “infinite” CPIs. Infinite CPIs are used to keep the effect of the memory hierarchy separate from the effect of the core design, so separate teams can work on both models in parallel. The effect of the memory hierarchy on the CPI has to be added in to the “infinite” CPI to get the overall CPI.

infL1CPI = CoreComponent + L1Component
infL2CPI = CoreComponent + L2Component + L2Component
and so on.

The calculation of infL1CPI assumes the L1 always hits, but has the normal hit latency. So it is an infinitely large L1, but miraculously the directory lookup and array access takes time equal to a realistic sized L1.
The calculation of infL2CPI assumes the L2 always hits, but has the normal hit latency. The L1 is realistically modeled, the L2 is the infinite L2 with correct hit latency modeled.

Going back to
CPI = CoreComponent + L1Component + L2Component + L3Component + MemComponent
Say we have cache models for the L1,L2, L2 caches and the memory. So how do we get the L1Component, L2Component, L3Component and MemComponent, such that we can get the overall CPI for the system. This is where the hitsPerInstruction and missesPerInstruction numbers come in very handy.
L1Component = L1ReferencePerInstruction * L1Latency –(A1)
L2Component = L2ReferencesPerInstruction * (L2Latency – L1Latency) –(A2)
L2Component = L3ReferencesPerInstruction * (L3Latency – L2Latency) –(A3)
MemComponent = MemReferencePerInstruction * (MemLatency – L3Latency) –(A4)

Notice that each component is a product of the fraction of instructions that reference that level and the amount of time those instructions which reference that level are guaranteed to spend at that lavel. Two observations here:
1. the ReferencesPerInstruction at each level is the sum of hitsPerInstruction and missesPerInstruction for that level
2. an easy way to determine the common amount of extra time introduced by a level into the overall execution of an instruction is to find the difference between the time when an instruction hits at that level and one level before.

Method 2: Breaking CPI into components for each level of the memory hierarcy an instruction finishes at

This method is often used when the aim is to simply calculate the overall CPI and we are not dealing with breaking the CPI into its CPI stack components.

CPI = CoreComponent + (L1HitsPerInstruction*L1Latency) + (L2HitsPerInstr*L2Latency) + (L3HitsPerInstr*L3Latency) + (MemHitsPerInstr*MemLatency) –(B)

Another way to say this is
CPI = Time spent by all instructions which do not have to even go to the L1Cache(s)
+ time spent by the fraction which hit L1 and face the L1Latency on top of the CoreComponent
+ time spent by the fraction which hit L2 and face the L2Latency on top of the CoreComponent
+ time spent by the fraction which hit L3 and face the L3Latency on top of the CoreComponent
+ time spent by the fraction which hit memory and face memory latency on top of the CoreComponent

Notice that each component looked at this way is the product of the fraction of instructions which hit in a particular level of the hierarchy and the time it takes to service those instructions.

CAVEAT: There is a distinct difference between the CoreComponent component in equations A and equation B. In equations A, CoreComponent applies to all the instructions, since all the instructions pass through the core. In equation B, the coreComponent applies to only those instructions which do not have to leave the core to access L1Cache (or caches, since Level 1 is usually broken into separate instruction and data caches). To simplify this, simulation models of the core often are tightly coupled with at least the L1cache or L1caches. There is a significant amount of overlap in accessing the caches, especially the level 1 cache and therefore the time spent in accessing one instruction or data granule might be able to hide the time to access another. This could adversely affect the CPI calculations. That is why this style of breaking up the CPI into its components and adding them up, only works as an estimate. A realistic CPI can only be realized by building in a more detailed understanding of the paralellism in a workload into the equations above, or by just creating a more accurate simulation model with the core model working hand-in-hand with the memory nest model. One way to make the above equations a little bit closer to reality is by only considering loads (i.e. both instructions and data loads) for the missesPerReference, hitsPerInstruction etc. Stores usually do not directly affect CPI since they are handled by mechanisms that are non-critical to CPI calculations.

Posted By: Anil Krishna at 2:30PM on Sunday, April 30th, 2006

Posted in Tutorials | No Comments »

PseudoLRU Replacement Scheme

October 10th, 2005 admin

I am taking ECE521, a Computer Architecture course at NCSU and am thoroughly enjoying it. One of the topics that was touched upon in the class, and with which I later struggled for a few hours was how pseudoLRU replacement policy works . I could not find useful tutorials on the net and decided to write one for myself. Feel free to use it as is if you find it helpful, or let me know and I can send you the ppt version.

Posted in Tutorials | No Comments »