Greedy Based Approach for Test Data Compression Using Geometric Shapes Essay Example for Free

Greedy Based Approach for Test Data Compression Using Geometric Shapes Essay As the complexity of systems-on-a-chip continues to increase, the difficulty and cost of testing such chips is increasing rapidly. One of the challenges in testing SOC is dealing with the large size of test data that must be stored in the tester and transferred between the tester and the chip. The cost of automatic test equipment (ATE) increases significantly with the increase in their speed, channel capacity and memory. As testers have limited speed, channel bandwidth and memory, the need for test data reduction becomes imperative. This project deals with lossless compression of test vectors on the basis of geometric shapes. It consists of two phases: i) Encoding or Compression and ii) Decoding or Decompression. During the compression phase we exploit reordering of test vectors to minimize the number of shapes needed to encode the test data. The test set is partitioned into blocks and then each block is encoded separately. The encoder has the choice of encoding either the 0‘s or the 1‘s in a block. In addition, it encodes a block that contains only 0‘s (or 1‘s) and x‘s with only 3 bits. Furthermore, if the cost of encoding a block using geometric shapes is higher than the original cost of the block, the block is stored as is without encoding. We have created a new greedy based algorithm to find the shapes present in a block in minimal time. This algorithm after analysis seems to be at least 50% more efficient than the algorithm proposed by the author of the original paper which has been implemented in our program. During the decoding phase the data is read from the compressed file and decoded based on the format in which it was encoded. These phases have been implemented using software. The application gives a good compression ratio of nearly 50% under average conditions, is extremely fast and the shape extraction algorithm used provides fast extraction of shapes. To test a certain chip, the entire set of test vectors, for all the cores and components inside the chip, has to be stored in the tester memory. Then, during testing, the test data must be transferred to the chip under test and test responses collected from the chip to the tester. One of the challenges in testing SOC is dealing with the large size of test data that must be stored in the tester and transferred between the tester and the chip. The cost of automatic test equipment (ATE) increases significantly with the increase in their speed, channel capacity and memory. As testers have limited speed, channel bandwidth and memory, the need for test data reduction becomes imperative. 1. 2 Systems on a chip A system on a chip or system on chip (SoC or SOC) is an integrated circuit(IC) that integrates all components of a computer or other electronic system into a single chip. It may contain digital, analog, mixed-signal, and often radio-frequency functions—all on a single chip substrate. A typical application is in the area of embedded systems. A typical SoC consists of: †¢ A microcontroller, microprocessor or DSP core(s). Some SoCs nbsp—called multiprocessor system on chip (MPSoC)—include more than one processor core. †¢ Memory blocks including a selection of ROM, RAM, EEPROM and flash memory. †¢ Timing sources including oscillators and phase-locked loops. †¢ Peripherals including counter-timers, real-time timers and power-on reset generators. †¢ External interfaces including industry standards such as USB, FireWire, Ethernet, USART, SPI. †¢ Analog interfaces including ADCs and DACs. Department of Computer Science and Engg, TKMCE Page 4 Greedy Based Approach to Test Data Compression using Geometric Shapes Voltage regulators and power management circuits. These blocks are connected by either a proprietary or industry-standard bus such as the AMBA bus from ARM Holdings. DMA controllers route data directly between external interfaces and memory, bypassing the processor core and thereby increasing the data throughput of the SoC. Figure 1 Department of Computer Scien ce and Engg, TKMCE Page 5 Greedy Based Approach to Test Data Compression using Geometric Shapes 1. 3 Data Compression Data compression, source coding orbit-rate reduction is the process of encoding information using fewer bits than the original representation would use. Compression is useful because it helps reduce the consumption of expensive resources, such as disk space or transmission bandwidth. On the downside, compressed data must be decompressed to be used, and this extra processing may be detrimental to some applications. For instance, a compression scheme for video may require expensive hardware for the video to be decompressed fast enough to be viewed as it is being decompressed (the option of decompressing the video in full before watching it may be inconvenient, and requires storage space for the decompressed video). The design of data compression schemes therefore involves trade-offs among various factors, including the degree of compression, the amount of distortion introduced (if using a lossy compression scheme), and the computational resources required to compress and decompress the data. Several test data compression techniques were proposed in the literature. These techniques can be classified into two categories; those that require structural information of the circuit and rely on automatic test pattern generation and/or fault simulation and those that are more suitable for intellectual property (IP) cores as they operate solely on the test data. Techniques of the first approach include some of the linear decompression-based schemes and broadcastscan-based schemes. Techniques of the second approach include statistical coding, selective Huffman coding , run-length coding , mixed run-length and Huffman coding , Golomb coding , frequency-directed run-length (FDR) coding , alternating run-length coding using FDR (ALT-FDR), extended frequency-directed run-length (EFDR) coding , MTC coding , variable-input Huffman coding (VIHC) , multilevel Huffman coding , 9-coded compression , Block Merging (BM) compression and dictionary-based coding . Test compression techniques in this class can be further classified as being test independent or test dependent. Test-independent compression techniques have the advantage that the decompression circuitry is independent of the test data. Changing the test set does not require any change to the decompression circuitry. Examples of test-independent compression techniques include Golomb coding, frequency-directed run-length (FDR) coding, alternating run-length coding Department of Computer Science and Engg, TKMCE Page 6 Greedy Based Approach to Test Data Compression using Geometric Shapes using FDR (ALT-FDR) , extended frequency-directed run-length (EFDR) coding , MTC coding , 9- coded compression and Block Merging (BM) compression 1. 4 Automatic Testing Equipment Automatic or Automated Test Equipment (ATE) is any apparatus that performs tests on a device, known as the Device Under Test (DUT), using automation to quickly perform measurements and evaluate the test results. An ATE can be a simple computer controlled digital multimeter, or a complicated system containing dozens of complex test instruments (real or simulated electronic test equipment) capable of automatically testing and diagnosing faults in sophisticated electronic packaged parts or on Wafer testing, including System-OnChips and Integrated circuits. ATE is widely used in the electronic manufacturing industry to test electronic components and systems after being fabricated. ATE is also used to test avionics and the electronic modules in automobiles. It is used in military applications like radar and wireless communication. . 4. 1 ATE in the Semiconductor Industry Semiconductor ATE, named for testing semiconductor devices, can test a wide range of electronic devices and systems, from simple components (resistors, capacitors, and inductors) to integrated circuits (ICs), printed circuit boards (PCBs), and complex, completely assembled electronic systems. ATE systems are designed to reduce th e amount of Figure 1. 2 test time needed to verify that a particular device works or to quickly find its faults before the part has a chance to be used in a final consumer product. To reduce manufacturing costs and improve yield, semiconductor devices should to be tested after being fabricated to prevent even a small number of defective devices ending up with consumer. Department of Computer Science and Engg, TKMCE Page 7 Greedy Based Approach to Test Data Compression using Geometric Shapes Chapter 2 2. 1 Problem Definition As the complexity of systems-on-a-chip continues to increase, the difficulty and cost of testing such chips is increasing rapidly. To test a certain chip, the entire set of test vectors, for all the cores and components inside the chip, has to be stored in the tester memory. Then, during testing, the test data must be transferred to the chip under test and test responses collected from the chip to the tester. Our application must be able to compress the test vectors by a significant percentage and it must also be lossless. In addition to these two basic requirements the program must extract the shapes from each block in an optimal manner (here the technique to be used is a greedy approach rather than a brute force one). Moreover the test data must be sorted and partitioned before shape extraction is done. The application must also be able to correctly decompress the encoded data. In order to obtain the shapes covering the bits in as little time as possible, we have created a greedy based algorithm which works in an overall time of O(n4). The original algorithm proposed by the authors of ? Test Data Compression based on Geometric Shapes? [1] on other hand requires one O(n4) operation to identify all possible covers and another O(n4) to find the optimal among them which is a brute force approach. 2. 2 Motivation for Project One of the challenges in testing SOC is dealing with the large size of test data that must be stored in the tester and transferred between the tester and the chip. The amount of time required to test a chip depends on the size of test data that has to be transferred from the tester to the chip and the channel capacity. The cost of automatic test equipment (ATE) increases significantly with the increase in their speed, channel capacity and memory. As testers have Department of Computer Science and Engg, TKMCE Page 8 Greedy Based Approach to Test Data Compression using Geometric Shapes limited speed, channel band-width and memory, the need for test data reduction becomes imperative. 2. 3 Problem Analysis The problem can be divided into the following phases 2. 3. 1 Test Set sorting Here sorting is done on the basis of its neighbors. Also to achieve maximum compaction the first vector after sorting must contain maximum number of zeroes. 2. 3. 2 Test Set partitioning Partitioning of test vectors into blocks can be done easily. But in the case of partial blocks which appears if the number of test vectors and size of test vectors are not integral multiples of N(block is of size N*N) we can partition the block as N*N and use a mark array to indicate which bits are not to be processed. . 3. 3 Shape Extraction Here the shapes must be extracted optimally which means we have to use a greedy algorithm. This algorithm was created and works superbly. 2. 3. 4 Decoding This is only a simple matter of finding the code and based on the code of filling up the test vectors. Department of Computer Science and Engg, TKMCE Page 9 Greedy Based Approach to Test Data Compression using Geometric Shapes Chapte r 3 3. 1 Encoding Phase 3. 1. 1 Test Set Sorting 3. 1. 1. 1 Description Sorting the vectors in a test set is crucial and has a significant impact on the compression ratio. In this step, we aim at generating clusters of either 0‘s or 1‘s in such a way that it may partially or totally be fitted in one or more of the geometric shapes shown in Table 3. 2. The sorting is with respect to both 0‘s and 1‘s (0/1-sorting). The technique is based on finding the distance D between two vectors A and B that maximizes the clusters of 0‘s and 1‘s. The next vector with the highest distance to the existing vector is selected during the sorting process. The distance D may be computed with respect to 0‘s (0-distance), to 1‘s (1-distance) or to 0‘s and 1‘s (0/1-distance) as follows: here k is the test vector length and W(Ai, Bi) is the weight between bits Ai and Bi. Table 3. 1 specify the weights used in computing the 0/1-distance between two vectors. Note that for i = 0, W(Ai, Bi-1) = 0 and for i = k 1, W(Ai, Bi+1) = 0. Table 3. 1 Department of Computer Science and Engg, TKMCE Page 10 Greedy Based Approach to Tes t Data Compression using Geometric Shapes Table 3. 2 3. 1. 1. 2 Algorithm 1. Find the vector with the maximum number of zeroes and interchange with first vector 2. i? 1 3. Compare ith vector with all other vectors from i+1 and calculate the distance based on the equation 4. Exchange the vector with maximum distance with ith vector 5. If ilt;n then i? i+1 Department of Computer Science and Engg, TKMCE Page 11 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 1. 2 Test Set Partitioning 3. 1. 2. 1 Description A set of sorted test vectors, M, is represented in a matrix form, R? C, where R is the number of test vectors and C is the length of each test vector. The test set is segmented into L? K blocks each of which is N? N bits, where L is equal to R/N and K is equal to C/N. A segment consists of K blocks. In other words, the test set is segmented into L segments each containing K blocks. For test vectors whose columns and/or rows are not divisible by the predetermined block dimension N, a partial block will be produced at the right end columns and/or the bottom rows of the test data. Since the size of such partial blocks can be deduced based on the number of vectors, the vector length and the block dimension, the number of bits used to encode the coordinates of the geometric shapes can be less than log2N. 3. 1. 2. 2 Algorithm 1. Partition the test vectors into 88 blocks( partial or full) 2. If block is partial then a. Mark the rest of the bit positions as already processed Department of Computer Science and Engg, TKMCE Page 12 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 1. 3 Shape Extraction 3. 1. 3. 1 Description This algorithm was created by our group to obtain the optimal covers of the shapes in as little time as possible. In our algorithm we begin by assuming that all other points before (i,j) has been processed. This means that if any new shape exists in this block it may only begin at a point greater than or equal to (i,j). Now if we are starting from (i,j) we need to check only four points adjacent to it along with (i,j). These positions are shown Figure 3. 1. This is a direct consequence of our initial assumption. Now let us assume that a shape begins from (i,j). Since no other shape has been detected so far, (i,j) is a point. Now the algorithm checks the four adjacent points to see whether the make any other shape when taken in combination with (i,j). Since (i,j) is classified as a point, the next possible shape that can be formed is a line. There are four possiblities for this. This is shown in Figure 3. 2. Figure 3. 1 Department of Computer Science and Engg, TKMCE Page 13 Greedy Based Approach to Test Data Compression using Geometric Shapes Now if another of the adjacent points is a valid bit and if the current shape s a line,then the next figure that can be formed from 3 points is a triangle. This also has four different possiblities. This is shown by Figure 3. 3. Figure 3. 2 If the current shape is a triangle(type 4) and if another point adjacent to (i,j) is of the bit we are checking for then, the only remaining possiblity is a rectangle. This is shown by Figure 3. 4. Figure 3. 3 In orde r to avoid the possiblity of rechecking bits that have already been processed our algorithm uses a ? mark‘ matrix similar to the block of bits,except that every position other than what has already been included in a shape are marked as zeroes. Those that have been identified as belonging to a shape are marked as ones. We also insert the points that have to be processed by the algorithm in the next stage into a queue for faster processing of the rest of the shape. Department of Computer Science and Engg, TKMCE Page 14 Greedy Based Approach to Test Data Compression using Geometric Shapes Figure 3. 4 The anomalies that can occur during this approach are: ? There can be other shapes starting from the same point (i,j). Since we are performing a greedy search, the only possiblity that comes under this category are additional lines emanating from (i,j). This can be easily solved by saving the current shape as well as the newly identified line into the list of shapes. Then the algorithm performs all the above mentioned steps, i. e. marking the bits processed and inserting the points to processed later into the queue. ? Another problem related with this simple approach is that the type 1 traingle may recognized as a rectangle and a few lines if its size is greater than one. This can be avoided by computing the length of the side of square that may contain the triangle(if it exists ) and the length of both the diagonals. If the length of a side is the same as that of a diagonal then its indeed a traingle or a square. To distinguish between these we check whether the length of both diagonals are same. If they are not, then the shape is a triangle,otherwise it‘s a rectangle. The reason these anomalies needs to be carefully implemented is that anomaly 2 can increase the computational complexity of our oerall algorithm significantly if its to be solved. Once the shapes have been detected for what they are we process only those positions that may be a continuation of the shape are processed. Also the proceesing of these bits are only done in the direction of interest(for example, in the case of say type 1 line the only possible extension of the shape occurs in the downward direction and hence this is the only direction processed). This means that not all of the four adjacent positions need to be checked during further processing, which in turn reduces complexity. Department of Computer Science and Engg, TKMCE Page 15 Greedy Based Approach to Test Data Compression using Geometric Shapes Once a shape has been completely detected, which begins from (i,j), we start the processing of the next bit at position (i,j+1) or (i+1,1). This is necessary so as to ensure that we do not miss any shapes during proceesing. Department of Computer Science and Engg, TKMCE Page 16 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 1. 3. 2 Algorithm Department of Computer Science and Engg, TKMCE Page 17 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 1. 3. 3 Complexity Analysis As we have seen the algorithm needs 3 loops. Out of this two is used to traverse the entire block. This gives us an outer loop complexity of O(n2). Then the third loop is always executed 4 times in order to check neighboring points. The actual detection of shapes is only a matter of addition of indices to (i,j) and checking to see whether they satisfy any of the conditions of the algorithm. Addition is done in constant time. Now although the detection of the kernel of shapes can be done in a constant time we need to spend some additional time in the case of anomaly 2. As mentioned earlier this can be solved by finding the length of the sides of the square containing it and the length of both the diagonals of the square. Also this must be the square that may contain the whole triangle. This means that in the worst case the lengths may be of size n. This gives us the complexity for this step to be 4O(n). The further processing of shapes that has been detected is done using a queue. The maximum number of times the queue can be executed is O(n2). This because there are at most that many bits in a block. Therefore the overall complexity for shape detection is O(n2) x4x(4O(n) + O(n2))=O(4n3 + n4)=O(n4). Now in average cases the queue will not need to contain the entire block, as the block can be assumed to be comprised of equal parts required and unrequired bits. This means that in the average case, shape extraction process predominates and average case complexity becomes O(n3). This is much better than a brute force approach to shape extraction. Even in the worst case our algorithm performs better as we do not need to perform a covering step to find the most optimal covers for the shapes detected. This would have taken another O(n4) which we avoid by directly using a greedy approach. Department of Computer Science and Engg, TKMCE Page 18 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 1. 4 Encoding 3. 1. 4. 1 Description The encoding process will be applied on each block independently. The procedure Extract_Shapes(b) will find the best group of shapes that cover the bits that are equal to b as shown in the algorithm. Encode_Shapes determines the number of bits, a, needed to encode this group of shapes. There are two cases that may occur: a) The block contains either 0‘s and X‘s or 1‘s and X‘s. In this case, the block can be encoded as a rectangle. However, instead of encoding it as a rectangle, it is encoded by the code 01‘‘ (indicating that the block can be filled by either 0‘s or 1‘s) followed by the bit that fills the block. Hence, the number of bits to encode the block a = 3. We call such blocks filled blocks. ) The block needs to be encoded by a number of shapes. We call such a block encoded block. In this case, we need the following: ? 2 bits to indicate the existence of shapes and the type of bit encoded. If the encoded bit is 0, then the code is 10, otherwise it is 11. ? P = 2 ? log 2 N ? 3 Bits to encode the number of shapes, S. If the number of shapes exceeds 2P, then the number of bits needed to encode the shapes is certainly greater than the total number of bits in the block. In this case, the block is not encoded and the original test data is stored. 3. 1. 4. 2 Algorithm 1. While there are shapes to be encoded a. Find shape and type of shape b. Find x,y coordinates of shape c. If shape has a length parameter calculate its value d. Depending on shape and type encode the parameters as per table 2. 2 Department of Computer Science and Engg, TKMCE Page 19 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 2 Decoding Phase 3. 2. 1 Description The pseudo-code of the decoding algorithm is given below. It first reads the arguments given by the encoder and computes the parameters needed for the decoding process. These parameters include the number of segments, the number of blocks in a segment and the dimensions of the partial blocks. For each segment, its blocks are decoded one at a time. The first two bits indicate the status of the block as follows: ? ? ? ? 00: the block is not encoded and the following N*N bits are the original test data. 01: fill the whole block with either 0‘s or 1‘s depending on the following bit. 10: There are shapes that are filled with 0‘s. 11: There are shapes that are filled with 1‘s. For those blocks that have shapes, the procedure Decode_Shapes is responsible for decoding those shapes. It reads the number of shapes in the block and then for each shape it reads its type and based on this it reads its parameters and fills it accordingly. Based on the arguments read first, the decoder can determine the number of bits needed for each variable (e. g. the coordinates and the distances). These are used for the partial blocks when only one block of each segment remains and when the last segment is being decoded. Department of Computer Science and Engg, TKMCE Page 20 Greedy Based Approach to Test Data Compression using Geometric Shapes 3. 2. 2 Algorithm Department of Computer Science and Engg, TKMCE Page 21 Greedy Based Approach to Test Data Compression using Geometric Shapes Chapter 4 4. 1 Language Specification The above project has been implemented in C/C++. This is because C/C++ is a language very well suited for bit level manipulations and provides other features which can be easily implemented using hardware directly. Another consideration that is of paramount importance here is the degree by which C/C++ lends itself to system level programming. The key considerations can be summed up as: ? ? ? ? ? ? Simple Very High Speed Very close to assembly language Can be used to directly implement application using hardware Bit level manipulations are possible Dynamic . 2 Hardware Specification CPU RAM Main Storage Medium Monitor : Pentium II or above : 4 MB : 1 GB HDD : Standard VGA 4. 3 Software Specification Operating System Design Tools : DOS : C/C++ Department of Computer Science and Engg, TKMCE Page 22 Greedy Based Approach to Test Data Compression using Geometric Shapes Chapter 5 5. 1 Application One of the challenges in testing SOC is dealing with the large size of test data that must be stored in the tester and transferred between the tester and the chip. The amount of time required to test a chip depends on the size of test data that has to be transferred from the tester to the chip and the channel capacity. The cost of automatic test equipment (ATE) increases significantly with the increase in their speed, channel capacity and memory. As testers have limited speed, channel band-width and memory, the need for test data reduction becomes imperative. To achieve such reduction, several test compaction and lossless compression schemes were proposed in the literature. The objective of test set compaction is to generate the minimum number of test vectors that achieve the desired fault coverage. The advantage of test compaction techniques is that they reduce the number of test vectors that need to be applied to the circuit under test while preserving the fault coverage. This results in reducing the required test application time. Department of Computer Science and Engg, TKMCE Page 23 Greedy Based Approach to Test Data Compression using Geometric Shapes CONCLUSION In order to check the effective compression ratio produced by the application several different test sets were taken and the algorithm was applied. The test vectors were sorted to maximize the compression. In this work, test vectors were sorted based on a greedy algorithm. Test vectors sorting based on the 0/1-distance was performed. For 0/1-distance sorting, the test vector with more 0‘s was selected as the first vector. The compression ratio is computed as: In the case of large vectors with only sparsely populated positions the application was found to produce very high compression ratio. In the average cases the compression ratio was nearly 50%.