芯片测试的DNA计算机算法研究

摘要：采用DNA超级计算，设计出芯片错误测试的有效算法，并将之与现有测试技术结合，解决现有集成电路中错误测试中存在因耗时过长而无法保证芯片电路准确率达到100%这一实质问题。最后阐述了芯片测试的DNA计算机算法研究的意义、现状、研究内容、研究方法等。

关键词：芯片测试；DNA计算；研究

中图分类号：TP384文献标识码：A文章编号：1009-3044(2008)23-1059-02

Chip Testing DNA Computer Algorithm Research

PAN Guo1, LI Ken-li2

(1.Hunan Modern Physical Distribution Professional Technology Institute, Changsha 410131, China; 2.School of Computer and Communication, Hunan University, Changsha 410082, China)

Abstract: Uses the DNA supercomputing, designs the chip wrong test the efficient algorithm, and with the existing test technology union, in the solution existing integrated circuit in the wrong test will exist because of lasts long has been unable to guarantee that the chip electric circuit rate of accuracy will achieve 100% this substantive question. This article elaborated the chip testing DNA computer algorithm research significance, the present situation, the research content, the research technique and so on.

Key words: chip testing; DNA computation; research

1 引言

DNA计算及DNA计算机的研究已成为近年来理论计算机科学的研究热点，是组合优化领域NP完全问题和其它难解问题的潜在解决方法之一。电路测试在集成电路研究领域中有着重要的地位，是大规模基础电路VLSI设计中的关键问题，但现有测试方法均要求高计算量，即使借助价格昂贵的超级计算机，依然难以满足实际应用对计算机芯片性能的强大需求。

2 研究意义

随着社会和科学技术的发展，许多新工程领域中的复杂系统不断出现，在这些复杂系统的研究过程中，各种棘手的NP-完全问题处处可见。电子计算机因运算速度和存储容量太小，无法对这些NP完全问题实现有效求解。生物分子计算或DNA计算的出现为这些难解问题的解决带来了新的希望，1994年Adleman博士首先在基于分子生化反应的基础上成功求解了7个顶点的Hamilton路径问题后，DNA计算与DNA计算机的研究形成了理论计算机科学、数学和生物学领域的一个新的研究热点， 吸引了众多计算机科学家和生物学家的研究兴趣，而可用DNA计算机解决的数学问题的种类也迅速增长。DNA 计算的最大优点是其具有的海量存储和并行运算能力，因此，它理论上可克服电子计算机存储量小与运算速度慢的不足。而且，只要未来关于DNA计算机的生物技术走向成熟（无错码、链长适中、操作自动化等），其超级计算的成本将远低于现有基于VLSI结构的超级计算机的成本：目前为止，一个测试试管已可产生1018个DNA链，它可使1018位数据以数据并行的方式并行运行。因此，DNA计算机可提供相当于1018个处理单元的并行性和O(1018)的存储空间。目前世界上最快的超级计算机在1000s内大约能并发处理128*1015位的信息，而DNA计算中耗时最长的“抽取”操作在1000s内可在试管中同时处理1018位的数据单元；DNA计算机的存储密度大约为磁带的1012倍。因此，利用DNA计算的巨大并行性，采用完全穷举的方式，仍然能够快速的找到激活故障所需的测试向量。

3 研究现状分析

随着集成电路技术不断发展，集成电路的规模越来越大，系统越来越复杂，单凭手工测试几乎是不可能的了，这迫使人们研究新的方法和技术来完成这项工作。随即计算机的出现，尤其是微型计算机的普及，为测试提供了物质基础，测试逐步从人工转向自动化。

随着各种数字系统尤其是数字计算机的飞速发展，集成电路得到了十分广泛的应用，其制造水平和工艺也随之迅速提高。为了保证系统运行的可靠性，集成电路测试技术成为了数字系统设计制造过程中非常关键的一环。然而集成电路的集成度，规模和复杂度呈现出几何级数的增长速度，这给电路测试带来了很大的难度，同时也出现了很多新的问题，一些传统的测试技术和方法已不能满足人们对系统可靠性的要求。要解决这些问题，迫切需要采用一些新的测试理论，测试技术和方法。

生物分子计算或DNA计算的出现为难解问题的解决带来了新的希望，1994年美国南加州大学的Adleman博士首先在基于分子生化反应的基础上成功求解了7个顶点的Hamilton路径问题[9]，并开创性地提出了DNA计算模型，之后，DNA计算与DNA计算机的研究形成了理论计算机科学、数学和生物学领域的一个新的研究热点，吸引了众多计算机科学家和生物学家的研究兴趣，而可用DNA计算机解决的数学问题的种类也迅速增长[10-12]。DNA计算的最大优点是其具有的海量存储和并行运算能力，因此，它理论上可克服电子计算机存储量小与运算速度慢的不足。而且，只要未来关于DNA计算机的生物技术走向成熟（无错码、链长适中、操作自动化等），其超级计算的成本将远低于现有基于VLSI结构的超级计算机的成本：目前为止，一个测试试管已可产生1018个DNA链，它可使1018位数据以数据并行的方式并行运行[13]。因此，DNA计算机可提供相当于1018个处理单元的并行性和O(1018)的存储空间。目前世界上最快的超级计算机在1000s内大约能并发处理128*1015位的信息，而DNA计算中耗时最长的“抽取”操作在1000s内可在试管中同时处理1018位的数据单元；DNA计算机的存储密度大约为磁带的1012倍。

到目前为止，利用DNA计算已经成功设计出许多数论及图论中NP难问题（如子集和、SAT、团问题等）；Chang利用基于粘贴模型首次提出破解 RSA 密钥的DNA算法；在工程应用方面，诸如电梯调度等NP难问题和数字信号处理也已在DNA计算中得到解决。

但是，利用DNA计算的巨大并行性，采用完全穷举的方式，对于大规模集成电路测试产生目前尚没有相应DNA计算机算法。

4 研究内容与研究目标

应用DNA生物超级计算所具备的海量并行运算能力，力图解决现有测试方法中计算能力不足问题。

1）利用DNA计算存在的巨大并行性，设计基于电压 测试产生的直接穷举的DNA计算机算法，结合生物实验与实际芯片对提出的算法进行测试和评估；

2）为了弥补电压测试的不足，进一步提高故障覆盖率，保证集成电路产品的高可靠性，设计基于电流测试产生的基于穷举的DNA计算机算法，结合生物实验与实际芯片对提出的算法进行测试和评估，通过与电压测试DNA计算机算法故障的覆盖率的比较，对所提出算法做进一步的改进；

3）从现有电子计算机中传统并行计算和并行处理的模型出发，分析DNA计算的基本生物操作的并行机制及其在并行方式和存储上所具有的特点，结合遗传算法、FAN算法等测试中的有效经典算法，考虑将传统并行处理的策略和DNA计算的特点相结合，提出可扩展新的DNA计算测试产生算法，算法应能显著降低DNA链长和DNA链数。

研究目标：利用DNA计算机模型，设计芯片错误测试的有效算法，解决现有芯片测试方法因为其要求的海量超级计算而无法保证测试准确率的问题。

5 采取的研究方法

1）DNA计算机模型的选取：针对芯片的功能部件及测试产生的特点，对目前主要的DNA计算模型进行综合比较与评价，并建立相应的评价体系，该体系能够充分考虑所要完成的各生物操作的功能、各功能在不同模型下实现的难易程度、生物操作本身的复杂度、DNA分子链的长度与问题规模间的关系和DNA计算中避免伪解和错解能力的高低等问题。 然后，选取一功能上完备的具有执行基本算术和逻辑运算能力即计算上完备的模型，该模型应该具有良好的可扩展性。

2）基本逻辑运算与基本算术运算的DNA计算机算法的设计：大规模的集成电路芯片都是由基本的算术、逻辑部件组成，因此首先设计基本逻辑运算和算术运算是最终测试算法设计的关键。 在正确选取了DNA计算模型之后，设计其相应的DNA计算机算法并运用实验手段进行分析改进。

3）集成电路中测试向量产生的DNA计算机算法设计：根据所选取的DNA计算模型及设计的基本算术及逻辑运算的DNA计算机算法，设计相应的基于DNA计算的集成电路测试向量产生的算法。同时，通过合作与交流，了解、借鉴和利用国内外最新DNA计算技术，用以指导求解上述问题的DNA计算机算法研究。

6 实验方案

实验上，采用生物分子计算研究所的普通PCR仪、DNA分子合成仪、杂交箱、测序仪、转移电泳槽、DN段分析系统、图像分析系统和电泳产品及各种生物酶等分子生物学的研究设备和研究药品，将设计的求解上述测试向量产生的DNA超级计算算法进行实验，将多次计算的结果在购置的以注入故障的芯片上进行测试，评估与分析，根据结果确认并完善理论成果，以达到预期研究目标。

1）针对芯片的功能部件及测试产生的特点，对目前主要的 DNA 计算模型进行综合比较与评价，并建立相应的评价体系并然后，选取一功能上完备的具有执行基本算术和逻辑运算能力即计算上完备的模型。

2）基本逻辑运算与基本算术运算的DNA计算机算法的设计并运用实验手段进行分析改进。

3）集成电路中测试向量产生的DNA计算机算法设计并通过在购置的已注入故障的芯片上进行测试评估。

7 结束语

本项研究首次将两者结合，试图利用DNA超级计算机的超级计算能力，解决电路测试呈指数增长的计算要求，具有明显的学科交叉性，将不仅为DNA超级计算开拓新的应用，还可探索为传统集成电路设计提供新的方法，具有相当的科学意义和应用价值。

参考文献：

[1] Keshavarzi A,Tschanz J,Narendra S. Leakage and Process Variation Effects in Current Testing on Future CMOS Circuits[J]. IEEE Design and Test of Computers, 2002,19(5):36-43.

[2] Braich R, S,Chelyapov N,Johnson C. Solution of a 20-variable 3-SATproblem on a DNA computer[J].Science, 2002,296(19):499-502.

[3] Chang W, Ho M, Guo M. Molecular solutions for the Subset-sum Problem on DNA-based Supercomputing[M]. BioSystems, 2004,73:117-130.

[4] Li K,Zou S,Xv J. Fast Parallel Molecular Algorithms for DNA-Based Computation[J].IEEE Transactions on Nanobioscience, 2005,4(2):133-163.