Advantages And Disadvantages Of Interlock Parity Information Technology Essay

Advantages And Disadvantages Of Interlock Parity Information Technology Essay Detecting and correcting errors is the major problem for handling on chip errors. For this purpose error detection and correction techniques are used which are suitable for NoC. Error control codes are used to detect single or multi bit errors. Errors correcting schemes put an overhead of extra hardware on the system. Most of the coding techniques are used to correct single bit error. Due to the increase in size and complexity of very large scale integrated (VLSI) chips the problem of multi bit errors have been increased, so to over come the problem of multi bit errors, researchers have explored various multi bit error detection and correction techniques. Multi bit errors can completely corrupt the packets which need to be discarded and retransmitted. As on chip errors are more dangerous than off chip networks more over on chip resources like storage and processing are limited, therefore techniques that take care such limitations are more appropriate for NoC. Here we are going to introduce a new error detection technique. This technique has the limitation of only detection of errors. We compare this technique with few other error detection and correction techniques and deduce the results about our purposed error detection techniques. We purpose the name of new error detection technique as Interlock Parity. In the next section the complete introduction and proposed format of the Interlock Parity is given. Next we look some advantages and disadvantages of Interlock Parity technique. 5.2 Interlock Parity This is a new purposed technique to detect the bit errors on the network on chip communication. This technique is designed to work with 32 bits of data word. After 8 bits of data next bit is fixed for parity bit. Similarly after that 8 bits the next bit is again fix for parity bit and in this way 32 bits of data include 4 parity bits. We name these parity bits as P1, P2, P3 and P4. The option for choice of even parity or odd parity is open i.e any method is used to fix the parity bit, but all 4 parity bits must follow the same parity scheme either even or odd parity checking. Similarly we name the first 8 data bits as d1, second data bits as d2, third data bits as d3 and last portion of data bits as d4. So after the induction of parity bits our date packet size will increase from 32 bits to 36 bits. Keep in mind there are few additional bits are reserved for the purpose of control information discuss in detail later in this chapter. Following figure 5.1 shows the packet layout of the Interlock Parity scheme. Header d1, Data bits (8 bits) P1 d2, Data bits (8 bits) P2 d3, Data bits (8 bits) P3 d4, Data bits (8 bits) P4 Figure 5.1 Interlock Parity packet format If number of 1s in d1 is even then P1 = 0 other wise 1. Next if number of 1s in d2 is even then the value of P2 is set to zero and bit value of P3 and P4 will be set according to the number of 1s in d3 and d4. More generally we can write as even then Pi = 0. where 1 à ¢Ã¢â‚¬ °Ã‚ ¤ i à ¢Ã¢â‚¬ °Ã‚ ¤ 4 If No. of 1s in di = odd then Pi = 1. where 1 à ¢Ã¢â‚¬ °Ã‚ ¤ i à ¢Ã¢â‚¬ °Ã‚ ¤ 4 Data block is transferred form source to the destination according to the control information header. At the destination first of all value of Pt is checked and if the Pt value is correct then the packet is accepted for further processing, in case of detection of some error in Pt bit value, process of evaluation of Pi values started. Each Pi value is checked according to the data present in di block. If there found any mismatch among di and corresponding Pi then di is discarded and retransmission request of that particular di is generated to resend the data. This reduces the probability of frequent bit flips in the data blocks. 5.3 Advantages and Disadvantages of Interlock Parity 5.3.1 Advantages of Interlock Parity Scheme Easy to calculate parities due to limited computation resources in NoC. In case of bit flip error detection only a limited portion of data needed to be retransmitted with in the packet. Easy to locate erroneous portion of data. Due to the probability of occurrence of multiple bit flip errors this technique of Interlock Parity restricts the multiple error occurrences in a byte size data. 5.3.2 Disadvantages of Interlock Parity Scheme Have to calculate 4 parity bits. Limited to detect errors if only single bit or odd number of bits flipped. Unable to detect errors if even number of bit flips occurred. This technique is not suitable for multiple errors. Errors correction is not possible at the receiver side. 5.4 Packet Format In this section we describe and closely look the format of the Interlock Parity scheme. Packet is divided into two portions. First portion is known as header and contains all the necessary information which uses to transfer packet from sender to the receiver. The second portion of the packet is known as data portion. In this section of the packet data is divided into 4 different parts along with the parity of each part. 5.4.1 Header Portion Header portion contains the following information. Source Address Destination Address Packet Number Data Portion Number Control Information Source Address field contains the information about the source and 5 bits are reserved for the source address. Destination address is the address of the destination and 5 bit are reserved for the destination address. Packet number denotes the number of the packet which is 10 bit long address. Data portion number denotes one of the four data portions in the date portion part. It can assume at the maximum 2 bits as we have maximum 4 data portions in our packet. 6 bits are reserved for control information can be used for future purpose or depend upon the routing algorithm requirements. Following figure depicts the structure of the header portion of the Interlock Parity packet format. Header Source Address Destination Address Packet Number Data Portion Number Control Information 5 bits 5 bits 10 bits 2 bits 6 bits Figure 5.2 Interlock Parity packet header format 5.4.2 Data Portion Data portion of the Interlock Parity packet format is divided into 4 parts. Each part is 9 bits long divided into 8 bits for the data and 1 bit for the parity bit corresponding to the data bits associated with the parity. In this way total size of the data portion along with parities is 36 bits. Following figure shows the structure of the data portion of the Interlock Parity packet format Data Portion d1 P1 d2 P2 d3 P3 d4 P4 8 bits 1 bit 8 bits 1 bit 8 bits 1 bit 8 bits 1 bit Figure 5.3 Interlock Parity packet data portion format. 5.5 Communication Strategy As during the communication of data packets, errors may corrupt the data so there is a need for reliable communication. Fundamentally few capabilities are required to handle the bit errors. Few of these fundamental capabilities to handle presence of bit errors are as mention below Error detection: A mechanism is needed to allow the receiver side to detect the occurrence of bit errors. There should be a mechanism which allows the receiver to detect and possibly correct bit errors. Receiver Feedback: since sender and receiver are typically executing at different nodes. The only way for the sender to know whether packet is delivered correctly to the receiver is by providing explicit feedback to the sender. For this purpose positive or negative acknowledgements are used by the receiver to sender. Retransmission: a packet received in error at the receiver will be retransmitted by the sender. Data packet is generated at the sender and sends to the receiver. At the receiver side checking of errors will take place, if packet received without any errors then it is accepted for further processing other wise packet is discarded. In case of any erroneous bits ARQ strategy will be used to correct the errors. As from the previous section our data portion of packet is divided into 4 data parts so only portion with errors in that data bits is requested to transmit again. We only use not acknowledgement (NAK) packet to communicate to sender for the retransmission of the particular erroneous portion of the data. Following figure shows the structure of the NAK packet format NAK Packet Source Address Packet Number Data Portion Number 5 bits 10 bits 2 bits Figure 5.4 NAK packet format. During the communication it does not allow reassembly or fragmentation at intermediate nodes. These operations can be performed at source and destination. As fragmentation and reassembly is a time consuming process, by removing this functionality from the intermediate nodes and placing it in the source and destination will definitely speeds up the communication. We implement interlock parity for end to end communication. Complete discussion and all the experimental results are presented in the next chapter. Chapter 6 Implementation and Experimental Results As discussed in previous chapters that network on chip provides a practicable way out to counter the incompetence of buses in the present very large scale integrated on chip interconnects. As we know in packet based communication a flipping error of bit(s) can corrupt the data packet which raise a question mark on the correctness and trustworthy of data transfer from source to destination. In the presence of stated problems it is essential to provide some vigorous protective solutions against such problems. As a solution to the above problems, network on chips have been proposed by different researchers to get rid of the ineffectiveness of on chip buses in scaling chips. Later it was discovered that network on chip also faces the same problems of transient faults as faced by VLSI chips. So chips designed with error detection and correction codes require high energy and area overheads as discussed in [65]. On network on chip we have limited resources of computation and storage; it is significant to present solutions which are low cost in term of memory and energy without compromising on reliability and performance. Here we are going to introduce a new error detection technique. This technique has the limitation of only detection of errors, while error correction takes place by retransmission of corrupt data packet. We compare our new purposed technique with few other error detection and correction techniques and deduce the results about our purposed error detection techniques. We purpose the name of new error detection technique as Interlock Parity. Complete introduction of Partial Party technique is given in chapter 5. In the next section the complete introduction about network on chip communication model, interest to use C/C++ and setup about implementation of Interlock Parity is given. We work on the different error detection methods given below, Simple Parity Cyclic Redundancy Check Checksum Mathod Repeated Bit Method along with our newly developed concept Interlock Parity method. We implement and present the implementation and comparative analysis results of Interlock Parity with above mentioned techniques. Major concern of this research is to make a comparative analysis between mentioned techniques in the following areas Encoding Techniques impact over the network throughput. Encoding Techniques impact for power consumption. Delay time comparison for packet delivery from sender to receiver i.e. latency comparison. Instead of using simulator we design our own network simulator designed in C/C++ program for the implementation purpose and get results for analysis. The purpose of personally designed simulator is to gain in depth working knowledge of different encoding techniques. 6.1 NoC Communication Model We use network on chip as 2 dimensional mesh topology with packet level communication. We use a data bus of size 128 bits which is wide enough to simultaneously transfer all bits of data present in the packet in any direction. As we discussed in chapter 5 packet consists of a header and data portion. The header contains identification information about source and destination, packet unique identifier, data portion identifier which varies from 1 to 4. Data portion of the data contains actual data along individual parity bits. Along with data packets we also use NAK packet. Sender will inform only in case of packet received with bit errors. NAK packet is also use to intimate the sender in case of packet loss. For the reasons of simplicity and well suitability for mesh based network on chips we adopt different routing strategies for the result analysis. NAK packet is assumed to have higher priority than data packet. Figure 6.1 2D Mesh [6] Data packet is generated at the sender and sends to the receiver. At the receiver side checking of errors will take place, if packet received without any errors then it is accepted for further processing other wise packet is discarded. We only use not acknowledgement (NAK) packet to communicate to sender for the retransmission of the particular erroneous packet/portion of the data. During the communication it does not allow reassembly or fragmentation at intermediate nodes. These operations can be performed at source and destination. As fragmentation and reassembly is a time consuming process, by removing this functionality from the intermediate nodes and placing it in the source and destination will definitely speeds up the communication. 6.2 Let Us C/C++ Instead of using simulator we design our own network simulator designed in C/C++ program for the implementation purpose and get results for analysis. The purpose of personally designed simulator is to gain in depth working knowledge of different encoding techniques. 6.2.1 Using C/C++ The C/C++ language is based on sequential programming, also suitable for the programming and modeling of concurrent activities. As we know most digital systems and hardware models require a notion of delays, clocks or time, such features are also present in C/C++ as a software programming language. So complex and detailed systems can be easily and comfortably designed in C/C++ language. Finally the data types present in C/C++ are helpful for implementation. To address all these problems new dedicated data types and communication mechanisms are available with C/C++. Basic language elements such as modules, processes, event, channels, and event driven simulator kernel are also present in C/C++. 6.2.2 Advantages of using C/C++ As C/C++ is firm programming language accepted all over the world, C/C++ holds all the features of a complete programming language which makes easier to write complex programs with minimum efforts. C/C++ supports all the data types supported by any language. C/C++ provides the facility of user friendly, which saves lot of money and precious time. C/C++ adds the idea of timing signals which is important to simulate synchronous hardware designs. This facility gives C/C++ an edge over other programming languages. C/C++ supports the design at higher abstraction level; this enables large systems to be modeled easily without worrying the implementation of it. C/C++ also support concurrency and can be used to simulate the concurrent behavior of the digital system. 6.3 Experimental Setup Instead of using simulator we implement Interlock Parity technique along with four other encoding techniques. For the implementation of Interlock Parity scheme, we use 2D mesh network topology. We use (4 X 4) mesh network at the initial stage of the experiment. To transfer all bits of the data simultaneously, we use 128 bits wide data bus in each direction. Figure 6.2 2D (4 x 4) Mesh [6] As we discuss the packet format in the previous chapter in detail. Our packet consists of 2 parts. One is header part and the other is data part also known as payload part. The header portion contains useful information like packet ID, source address, destination address, routing information, total nodes in the network and some control information etc. the payload or data portion holds the original data. Further in our implementation of Interlock Parity scheme, we categorize packets into two classes. Data packets Control packets As data packets hold useful data, while control packets contains information about the reliable delivery of the data packet send from some source to the destination. For the simplicity we only use negative acknowledgment (NAK) control packet. How this mechanisms work is illustrated below If data packet received with out any error at the destination, then accepted and no acknowledgement is send back to the sender. If data packet received with any error at the destination, then packet is discarded and NAK is send to the sender requesting the source node to send the packet again. This research also take care the lost packet impact on encoding technique. 6.3.1 Lost packet If some packet is lost on the way from source to destination, say packet n is lost, NAK is send to sender informing about not receiving the packet n. this packet is resend to destination after receiving NAK about packet n. 6.3.2 Lost NAK packet If some NAK packet lost, then after some time interval same NAK is send again until desired packet received. Following algorithm illustrate the communication between sender and receiver Packet Generate Send to Destination Error Yes NAK Accepted Queued No Figure 6.3 Flow diagram For better result purpose we implement our encoding techniques on the following routing strategies. X-Y routing Path Exploring(P.E) routing Gossip routing 6.4 Experimental Results 6.4.1 Clock Cycles Analysis On over own designed network simulator we first simulate a single packet and compute the computer clock cycles for the following phases of the packet. For the construction of header portion of the packet For the construction of the data portion of the packet Clock cycles required to put encoding check at the packet Clock cycles required to check data integrity at receiver side Clock cycles required for retransmission of packet for unreliable delivered packet In case of packet loss , clock cycles required to enforce the mechanisms to find out lost packet To achieve the above mention objective we send a packet on our designed network simulator. Our network simulator is equipped with reliable, unreliable and packet loss mechanisms. We randomly choose a sender and sender send a packet for randomly chosen destination node. Initially we ignore time for the network traversal and up till now our objective of this module is to gather the clock cycles for the formulation of packet, clock cycles required for enforcing encoding technique , rechecking the integrity of data and clock cycles required to handle the packet loss scenario. To get more accurate result we perform this simulation module for 10 times and average results are presented in the following table 6.1 Sr.No Algorithms Header Portion Data Portion Encoding Technique Reliable Delivery Unreliable Delivery Packet Loss 1 Simple Parity Checking 2 4 1 3 7 6 2 Cyclic Redundancy Check 4 8 10 10 20 13 3 Repeated Bit Method 2 12 2 4 10 8 4 Checksum Method 2 10 5 7 16 10 5 Interlock Parity Checking 3 6 4 6 14 9 Table 6.1 Clock cycle breakdown Clock CyclesFigure 6.4 Clock cycles breakdown The above analysis shows the comparison of clock cycles consumed by different encoding technique for different phases of packet construction and for checking and enforcing the encoding techniques. It is very clear from the above analysis that Cyclic Redundancy Check encoding technique takes longer time to impose the header and data portion part. Similarly CRC technique also takes longer clock cycles for the enforcement of encoding technique mechanisms. Similarly it is clear from the above analysis that checksum method encoding technique takes longer time to impose the header and data portion part. Similarly checksum technique also takes longer clock cycles for the enforcement of encoding technique mechanisms. Our new purposed Interlock parity check technique consume relatively less clock cycles for header and data portion. Thats means packet construction is relatively fast in out new purposed technique. In case of reliable delivery Interlock parity scheme again consume less clock cycles and has an advantage over the CRC and checksum method. While in unreliable delivery checking case Interlock parity scheme again consume less clock cycles and has an advantage over the CRC and checksum method. Lastly in packet loss handling scenario Interlock parity scheme consume 14 clock cycles which is less than from the clock cycles consumed by checksum method and CRC. The other two techniques simple parity and repeated bit method are consuming less clock cycles, but remember these clock cycles are required for the construction and enforcement of encoding techniques only. Network traversal i s not included up till this point of research. Next we present the percentage utilization of clock cycles for the sender node and for receiver node. Following table shows the result comparison for sender and receiver. Receiver Sender Sr.No Algorithms Header Portion Data Portion Encoding Technique Reliable Delivery Unreliable Delivery Packet Loss 1 Simple Parity Checking 28.57 57.14 14.29 18.75 43.75 37.50 2 Cyclic Redundancy Check 18.18 36.36 45.45 23.26 46.51 30.23 3 Repeated Bit Method 12.50 75.00 12.50 18.18 45.45 36.36 4 Checksum Method 11.76 58.82 29.41 21.21 48.48 30.30 5 Interlock Parity Checking 23.08 46.15 30.77 20.69 48.28 31.03 Table 6.2 Clock cycles breakdown for the sender and receiver side. Table 6.2 shows the clock cycles breakdown for the sender and receiver side. These results are also shown graphically in Figure 6.5. This graphical analysis consists of three compariosions Header portion comparision Data portion comparision Implementation of encoding technique During the construction of header portion our proposed technique required little larger time as compared to the other techniques. Reason is that header of our proposed technique require little extra bits to take care about different data segment with in a packet as disscussed in previous chapter. But uptill this point we can tolerate this large time for the construction of header as variance of timings for all techniques range between 10 to 30 clock cycles. As header portion contains small portion of packet so we can accept this drawback of interlock parity scheme. When we look at the data portion timing overhead comparisions, it is very clear that our proposed technique required less amout of time for the construction of data portion in the packet. As data portion consists of more bits of data then it is an advantage of our proposed tehnique for utilizing less clock cycles for the construction of data portion. Finally for the implementation and enforcement of encoding technique our proposed interlock parity checking technique requires comparatively balanced clock cycles. For this comparision we can say that our technique utilize less clcok cycles at the sender side for the administrative steps. Clock Cycles (%)Figure 6.5 Clock cycles breakdown for sender side Similarly at the receiver side we check three different scenarios. Clock cycles required to check whether packet received in reliable delivery Clock cycles required to check the unreliable delivery of the packet Clock cycles required to invoke the verification module about the loss of a packet. These statistics are depicting in the Figure 6.6 below. In this comparison it is clear that all encoding techniques required almost same amount of clock cycles for the implementation of above mention sceneries. Our proposed technique has an advantage of other compared techniques in the case of packet loss. In case of packet loss interlock parity scheme required comparatively less clock cycles to invoke the packet loss module. In case of unreliable packet delivery all mentioned techniques required same number of clock cycles. There is little variation among the encoding techniques which is neglectable. Clock Cycles (%) Figure 6.6 Clock cycles breakdown for receiver side Sr.No Algorithms Reliable Delivery Unreliable Delivery Packet Loss 1 Simple Parity Checking 0.2747 0.3846 0.3571 2 Cyclic Redundancy Check 0.8791 1.1538 0.9615 3 Repeated Bit Method 0.5495 0.7143 0.6593 4 Checksum Method 0.6593 0.9066 0.7418 5 Interlock Parity Checking 0.5220 0.7418 0.6044 Table 6.3 Encoding mechanism checking time measured in seconds Next we present the time required for different encoding techniques at sender side. As we see from the output results given in Figure.6.7 in case of reliable delivery our proposed interlock parity checking technique needs less time as compared to other encoding techniques. In case of unreliable delivery all the encoding techniques require large amount of time as compared to reliable delivery case. In this comparison interlock parity scheme has advantage over CRC and Checksum method. While repeated bit takes approximately same time as taken by interlock parity scheme. Simple parity checking technique is the only technique consume less time as compared to others. Reason is being its simple nature. In packet loss case our proposed technique less time as compared to the other techniques. So after this comparison we can say that interlock parity checking consumed less amount of time. Time Figure 6.7 Encoding Mechanism checking time measured in seconds If we look this comparison in different way, then the following Figure 6.8 gives the comparison of different encoding techniques in the context of reliable delivery, unreliable delivery and packet loss scenario. Simple parity checking encoding technique takes less amount of time as compared to other encoding techniques. In the contrast interlock parity checking technique consume less amount of time as compared to CRC, repeated bit method and checksum method. TimeFigure 6.8 Encoding Mechanism checking Time measured in seconds 6.4.2 Encoding Techniques and Routing Strategies Analysis In the all above discussion we are not considering network delays and routing strategies. To check the performance of encoding techniques we implement these techniques on different network strategies. These routing strategies include Encoding technique with XY routing strategy Encoding technique with PE strategy Encoding technique with gossip routing strategy For better results we further adopt two methods for the enforcement of encoding techniques. One is end to end (E2E) and second is node to node (N2N). In E2E strategy packet is checked only at the destination node, no checking is made at the intermediate nodes. This technique has an advantage of less traffic congestion. While in node to node strategy incoming packet is checked at each and every intermediate node. Packet is discarded as found in error. Forwarding node is intimated and retransmission takes place. This technique faces the problem of network resources and network congestion. We make different comparisons for above mentioned strategies for both E2E and N2N cases. 6.4.2.1 Encoding Techniques and XY (E2E) Routing Strategy Following table 6.4 shows the results of encoding techniques with E2E XY routing strategy. Table 6.4 gives the clock cycles required for different encoding techniques for different cases e.g. reliable delivery, unreliable delivery and packet loss. Sr.No Algorithms Simple Parity Checking Cyclic Redundancy Check Repeated Bit Method Checksum Method Interlock Parity Checking 1 Reliable Delivery 18 40 26 32 27 2 Unreliable Delivery 28 56 40 47 41 3 Packet Loss 27 49 38 41 36 Table 6.4 Encoding technique with XY (E2E) Strategy Figure 6.9(a) present these results graphically. Our proposed technique consumes less clock cycles as compared to other encoding techniques. Simple parity check is the only technique which has advantage over our proposed technique. But interlock parity check technique has advantage over all other techniques other than simple parity check techniques. Clock Cycles Figure 6.9(a) Encoding technique with XY(E2E) Strategy Figure 6.9(b) present these results graphically in other context. In case of reliable delivery our proposed technique consumes less clock cycles as compared to checksum method and CRC. While for repeated bit method case, the comparison is almost same. Simple parity check method has little advantage over interlock as well as other encoding techniques. When we come towards the analysis of unreliable delivery case, this segment takes more time as compared to the reliable delivery scenario. Our proposed technique also consume less clock cycles as compared to other encoding techniques other than simple parity check method. Packet loss case takes more time than reliable delivery but consumes less clock cycle