从物理限制和技术实现两方面来看,传统的互补金属氧化物半导体(Complementary Metal-Oxide-Semiconductor-CMOS)集成电路正在迅速接近其尺度极限。新兴的纳米电子器件技术和其所对应的纳米电子结构技术被认为可以(短期)补充甚至(长期)替代CMOS技术。纳米电子技术有望实现极高的器件密度(1012/cm2)和操作频率(超过100GHz),不仅使得进一步延伸摩尔定律成为可能,同时也展现出未来计算系统中存在的巨大机遇。然而挑战总是和机遇并存。纳米电子系统的设计和制造面临一系列新的问题,如极高的器件缺陷密度、局部互连限制、新的逻辑表达形式、以及运行时的高瞬态错误率等。对纳米电子系统所面临的一系列新挑战的认识,是人们向构建功能型纳米电子系统迈出的第一步。而纳米电子器件极小的尺寸和严重的不可靠性,对设计自动化技术提出了新的、严苛的要求,成为当前电子科学和工程所面临的新挑战。近年来,纳米电子系统的可靠性设计开始成为电子设计自动化和可靠性测试领域一个新的研究热点,工作主要集中在容缺陷设计和容错设计两个方面。本文研究纳米电子系统的容缺陷设计方法。面对纳米电子系统极高的缺陷密度,为了保证纳米芯片的可用性,未来的纳米芯片设计和制造工业迫切需要有效的容缺陷设计技术。有两种可能的设计模式：应用相关的设计模式(Application-dependent design)和应用独立的设计模式(Application-independent design)。前一种模式直接将逻辑函数映射到存在缺陷的Crossbar结构中,实现逻辑计算功能；后一种模式则先从有缺陷的Crossbar中提取无缺陷子结构,再在无缺陷子结构上实现逻辑映射。本文对这两种设计模式所涉及的问题和算法进行了系统深入的研究,主要工作和成果归纳如下：1.系统地研究了基于纳米Crossbar结构的容缺陷逻辑映射问题及其算法。应用相关设计模式的核心步骤是容缺陷逻辑映射(Defect-tolerant logic mapping-DTLM)。本文对DTLM问题模型及其求解算法进行了探索性研究,包括：1)在算法设计方面,针对此前的贪婪容缺陷逻辑映射算法映射成功率低的不足,引入多样性映射的概念,并提出了三种基于多样性映射机制的容缺陷逻辑映射算法。实验结果显示,所提算法的映射成功率是传统的贪婪映射算法的几倍到十几倍,并且在大规模问题上性能改进尤其明显。2)在问题建模方面,对一种面向模块化功能映射的DTLM问题进行了研究,设计了一种新的,更为合理的权值覆盖率优化模型,与之前的工作相比,新模型考虑了逻辑函数的具体细节,买验结果表明,新模型可以更准确地估计实现给定逻辑功能所需的纳米Crossbar模块数。2.提出了一种基于Memetic算法(Memetic Algorithm-MA)和适应度近似策略(Fitness Approximation-FA)的容缺陷逻辑映射算法。容缺陷逻辑映射(DTLM)问题可以抽象为两个二部图之间的子图同构问题(Subgraph isomorphism problem-SIP),是一个著名的NP完全组合搜索问题。本文通过引入最大二部匹配(Maximum-Bipartite-Matching-MBM),首次将DTLM问题建模成一类组合优化问题。基于该优化模型,本文提出一种高效率的基于Memetic算法和适应度近似策略的容缺陷逻辑映射算法, MA/FA。在MA/FA中,设计了一种新的贪婪重分配局部搜索算子(Greedy Re-assignment Local Search-GRaLS),利用问题的领域知识和信息来帮助算法以相对较低的计算代价找到最优的逻辑映射方案。此外,提出采用精确MBM算法和近似MBM算法相结合的适应度评估机制来降低算法适应度评估的计算代价,引入一种混合策略来平衡适应度评估的精确性和时间效率。通过在大量不同规模测试问题上的实验,验证了MA/FA算法的优异性能。3.系统地研究了从有缺陷纳米Crossbar结构中提取无缺陷子结构的问题。应用独立的容缺陷设计的关键在于无缺陷子结构的快速提取。对于所有在相同制造环境(相近的缺陷密度p)中制造的纳米芯片,无缺陷子结构的尺寸k是相同的。为了得到在利用率和产率之间的平衡,制造商需要知道k值是如何影响产率的：给定Crossbar结构尺寸n和缺陷密度p,存在尺寸为k的无缺陷子结构的概率为多少?此前只能通过实验仿真来估计。本文提出一种无缺陷子结构存在概率Pexist的分析方法,能估计出其紧凑的上界和下界。通过实验仿真验证了所提分析方法的有效性。4.提出了一种快速无缺陷子结构提取算法。通过对此前两种有效算法的思想进行融合,提出一种较低时间复杂度的改进算法。在此基础上,进一步通过减少算法主循环的次数,提升算法的时间效率,进而提出一种快速的无缺陷子结构提取算法。与此前最有效的算法相比,所提快速算法的时间复杂度从O(n3)降低到O(n2)。通过大量不同尺寸和缺陷密度的测试实例对算法性能进行了测试,结果表明所提快速算法可以提供与此前最有效算法相同质量的解,而算法的运行时间只是其1/3-1/5。5.提出了一种基于演化算法(Evolutionary Algorithm-EA)和结构变异(Structure Mutation-SM)的无缺陷子结构提取算法。无缺陷子结构提取问题等同于最大平衡Biclique问题(Maximum Balanced Biclique Problem-MBBP),是一个著名的NP难组合优化问题。针对MBBP问题,本文提出了一种新的基于结构变异的演化算法,EA/SM。在EA/SM中,结构变异算子在动态改变解的结构的同时,保持解的尺寸(适应度)和合法性不变。结构变异算子实现了解在MBBP问题结构空间的一种大变异,有益于增强启发式搜索过程中算法的探索能力。此外,针对MBBP问题特点,设计了一种高效启发式搜索算子。采用一种基于修复辅助的重启过程,利用改进的Marchiori启发式修复算子,修复每个重新初始化的新解。通过大量不同尺寸和缺陷密度的测试实例对算法性能进行了测试,实验结构验证了EA/SM算法的先进性能、以及结构变异算子和修复辅助重启的有效性。本文工作对未来纳米电子系统设计自动化(Electronic Design Automation-EDA)技术的发展具有一定的推动意义。