-1-
基于 DNA计算的并行处理系统
杨锐
北京邮电大学计算机学院体系结构中心，北京 (100876)
摘 要：DNA 计算机以其高度并行性，运算速度快，存储容量大，能量消耗低等特点成为
新一代计算机的候选之一。但是由于大量 DNA分子的控制、辨别复杂，无法高效地从候选
结构中检测和筛选结果等缺陷，使 DNA计算机的实现非常困难。另一方面，随着电子技术
和集成电路技术的发展，使得硬件电子电路的成本降低。本文提出了一个新的并行系统，可
以结合 DNA计算和集成电路二者的优点，在实验室已设计出的系统基础上，用 FPGA实现
系统主体框架，将控制器部分从 FPGA剥离出来，用单片机实现，扩大了原有系统的规模，
借用 DNA计算的步骤，采用大规模并行计算，引入四值逻辑实现地址转换器，解决了一个
10变量的 SAT问题。
关键词：DNA计算 并行处理系统 FPGA 单片机 SAT问题
中图分类号：
1．引言
自电子计算机发明以来，在几十年中，已经取得了很大的发展，运算速度的提高，存储
容量的扩大，使其功能更加强劲。电子计算机的发展，归功于关键性的两个历史性事件：一
个是现代计算机体系结构理论的建立；另一个是集成电路的发明。电子计算机计算能力的提
高主要体现在芯片技术的进步上，随着单位面积内硅芯片上集成的晶体管数目不断增大，计
算机的计算能力不断增强。
但是，芯片上元件的几何尺寸不可能无限制地缩小下去，这就意味着芯片单位面积上可
集成的元件数量会达到极限，摩尔定律不再适用。另一方面，人们对计算机的要求越来越高，
对于那些复杂的非线性数学物理方程进行大规模和高精度的计算，传统计算机往往是无能为
力的。
基于以上原因，人们需要从新的途径来进一步发展计算机，比如采用新的制造材料，或
者提出新的体系结构。
DNA计算机便是可以取代硅芯片计算机的方案之一。自1994年Adleman在《科学》期刊
上发表了第一篇关于DNA分子算法的开创性文章以来，DNA计算迅速成为活跃的研究领域
[1]。在这篇文章中，Adleman通过生化方法求解了七个结点的Hamilton问题，证明了用DNA
进行计算的可行性，同时引起了包括生物界、数学界、计算机领域科学家的广泛关注。DNA
计算有以下几个方面的优点[2] [3] [4]：
（1）高度的并行性，运算速度快；
（2）巨大的存储容量；
（3）非常低的能耗；
然而，DNA计算机毕竟还是一种理论设想，实际设计一个DNA计算机还有有一些障碍
的 [4] ：
（1）构造的现实性以及计算潜力
（2）运算过程中的错误发生与传播
（3）人机界面
在当前的DNA计算框架中，DNA串表达的计算状态类似于并行机的芯片状态，并行计
算中用的算法通常依赖与并行计算单元之间的通信，目前还没有DNA串之间通信的方法，
-2-
所以常规的并行计算技术还不能用于DNA计算[4]。
那么，随着电子技术发展很成熟，大规模集成电路的成本不断下降，我们可以尝试把集
成电路成本低廉，制造工艺成熟的特点与DNA计算的优点相结合，设计一个以FPGA来作为
模型主体，单片机来作为控制器的新型的并行处理系统。
2．DNA计算
在说明并行处理系统之前，先对 DNA计算的基本思想和步骤做一个简单的介绍。
DNA 计算是一种以 DNA 与相关的某些生物酶等作为最基本材料的、基于某些生化反
应原理的一种新型的分子生物计算方法。它的基本思想[5]是：利用 DNA 特殊的双螺旋结构
和碱基（腺嘌呤 A、胞嘧啶 C、胸腺嘧啶 T、鸟嘌呤 G）互补配对规律进行信息编码，把要
运算的对象映射成 DNA分子链，在生物酶的作用下，生成各种数据池，然后按照固定的规
则将原始问题的数据运算高度并行地映射成 DNA分子链的可控的生化过程，最后利用分子
生物技术检测所需要的运算结果。计算一般可以概括为 3个基本步骤[3]：
(1)分析要解决的问题，采用特定的编码方式，将该问题反映到 DNA链上，并且根据需
要合成 DNA链；
(2)根据碱基互补配对的原则进行 DNA链的杂交，由杂交或者连接反应执行核心处理过
程；
(3)得到的产物即为含有答案的 DNA 分子混合物，用提取法或破坏法得到产物 DNA。
如果问题比较复杂，经过一轮处理只能得到中间结果，那么可转至步骤(2)继续执行，直到
得到满意的结果为止。
3．基于DNA计算的并行处理系统
从前面的介绍可以知道，DNA 计算和电子计算都有着各自的优缺点，那么，我们可以
尝试综合二者的优点，设计出一个新的并行处理系统，来解决一些适合 DNA计算解决的问
题，比如 SAT问题。
由于实验室之前有过此类的尝试，是一个完全用 FPGA 来实现的并行系统，但是由于
FPGA芯片上的资源有限，若控制器和计算阵列都由 FPGA来实现的话，系统的规模受限，
无法体现出 DNA计算大规模并行计算的特点。
所以，我们尝试，并行系统的控制器由单片机来实现，并行系统的计算阵列由 FPGA来
实现，这样可以节省 FPGA一部分资源，从而可以将并行系统的规模尽量放大，将大规模并
行性的优点体现出来。
本文中的并行处理系统针对 SAT问题设计，是一个可以解决 10变量 SAT问题的系统。
是并行系统的一个特例。下面是对这个针对 SAT问题设计的并行系统的详细介绍。
系统框架
基于 DNA计算机的特点，并行计算系统主要分为控制模块和并行处理模块。
1)控制模块由单片机 AT89S52 实现。主要是像并行处理模块发送相关的控制信号并且
接收并行处理模块的反馈信号然后做出相应的处理；
2)并行处理模块由 Xilinx 公司的 FPGA芯片 Spartan II xc2s200实现。该模块是整个系
统的主体，由四部分组成，包含有地址转换器、数据发生器部件、并行存算阵列和读写系统。
系统框架如下图所示：
-3-
图1.系统框架图
由于本文中的系统是针对 SAT 问题设计，虽然并行存算阵列中的功能单元规模大，数
量多，但是功能简单，只有读写功能。所以实现本系统的时候，数据发生器可以不要，对功
能单元的读写可以通过读写系统来完成，本系统的框架图如下所示：
图2.文中实现的系统框架图
控制模块和指令
控制模块
控制模块模块相当与传统计算机中的 CPU部分，控制并行处理模块的运行，根据从存
储器中读出的指令，发送相关控制信号给并行处理模块。
系统运行的控制信号由控制器发送，使用单片机 AT89S52 作为控制器，将要执行的指
令预先写入单片机开发板上的
2E PROM 中,在系统运行时，单片机从
2E PROM 中顺序读
取指令，解析指令后将相应的控制信号发送给 FPGA，FPGA中的并行处理系统在接收到信
号后开始工作。
由于这部分是单片机实现，所以免去了设计状态机的复杂，单片机和 FPGA的管脚直接
通过导线连接，预先给出要执行的指令条数，根据指令给单片机相应的管脚赋值，即发送控
制信号，然后检查计数器，确认所有指令是否都已执行，若全部都已执行，则保持在最后一
条指令的状态，否则继续从存储器取指令，继续执行。
其工作流程如图所示：
-4-
图 3.控制模块工作流程
指令
由于本文中的系统是针对 SAT问题设计的，功能单元的设置比较简单，只有读写功能，
所以只需要读、写两种指令。
两条指令的格式如下所示：
1） 读指令
7 6 5 4 3 2 1 0
Byte 1 1 0 0 0 X X X X
Byte 2 X X X X X X X X
Byte 3 X X X X X X X X
表 1. 读指令格式
位
数 字 节 数
-5-
从表格中可以看出，读指令总共有 3个字节。下面说明 3个字节的作用：
Byte1：第 7位和第 6位为 10，表示该指令是读指令；第 5位和第 4位默认为 0，
在读指令中没有意义；第 3位到第 0位是地址的高 4位；
Byte2和 Byte3：这两个字节均为地址，他们和 Byte1中的低 4位拼接成一个 20位
的地址。
2） 写指令
7 6 5 4 3 2 1 0
Byte 1 0 1 0 X X X X X
Byte 2 X X X X X X X X
Byte 3 X X X X X X X X
表 2. 写指令格式
与读指令相同，写指令也有 3个字节。各个字节作用如下：
Byte1：第 7位和第 6位为 01，表示该指令是读指令；第 5位默认为 0，在读指令
中没有意义；第 4位表示写指令要往指定处写的数据，是 1还是 0；第 3位到第 0位是
地址的高 4位；
Byte2和 Byte3：这两个字节均为地址，他们和 Byte1中的低 4位拼接成一个 20位
的地址。
从上面对指令的介绍中可以看出，当系统运行时，输入的指令是大量的二进制串，
如果完全通过人工方式书写，虽然可以完成，但是容易出错，所以，我们规定了一些助
记符，编写了一个汇编器，可以让汇编器把用助记符书写的指令直接“翻译”成系统可
以识别的二进制代码，这样就可以避免人工输入时因粗心引起的错误。
因为只有两条指令，所以助记符也只有两个，分别是：
1）rd XXXXXXXXXX
对应读指令，rd后面接一个空格，后面的 10个 X是地址，汇编器会将其翻译成系
统可识别的 20位地址。
2） wr X XXXXXXXXXX
对应写指令，wr 后面接一个空格，后面的 X 表示要写入的数据，是 1或者 0，再
接 10个连续的 X，表示地址，汇编器会将其翻译成系统可识别的 20位地址。
汇编器的实质是一个状态机，其工作过程如下：
图 4. 汇编器工作流程
位 数 字 节 数
-6-
并行处理模块
并行处理模块部分用 Xilinx 公司的 FPGA芯片 Spartan II xc2s200实现。由四个部分组
成，这四个部分是地址转换器、数据发生器、并行存算阵列和读写系统。每个部分都有自己
的特殊职能，其中地址转换器和数据发生器的结构类似，但是作用完全相异，这二者都使用
了四值逻辑；并行存算阵列是本系统的核心，由很多相互独立的功能单元组成，每个功能单
元即可以运算又可以临时存储结果，避免了存储器瓶颈；读写系统用来负责对最后结果的读
出，也可以完成一些特定的写功能。下面是对各个部分的详细介绍。
并行存算阵列
该阵列由 2n个完全相同的功能单元组成，每个功能单元彼此之间相互独立。它们既有
运算功能，也有存储数据的功能。运算时，先通过地址转换器选中要工作的功能单元，选中
的工作，未选中的不工作。然后将操作数通过数据发生器（也可以通过读写系统）发送至功
能单元，计算出来的结果存储在功能单元内部的存储其中。
受所选器件资源的影响，如果实现大规模的模型，每个功能单元的功能就简单，最简单
的就是一个 D 触发器；如果实现小规模的模型，每个功能单元的功能就相对复杂一些，可
以具有算术逻辑运算功能。
在本文中实现的系统是针对 10 变量的 SAT 设计的，所以 n=10，并行存算阵列中总共
有
102 即 1024个相互独立的功能单元。由于在本系统中每个功能单元只有读、写两种功能，
所以这 1024个功能单元本质上是 1024个 D触发器。
图 5. 功能单元
图 5是本文中实现的系统中，并行存算阵列中的功能单元，D是输入单元的数据，CLK
是时钟信号，CE是片选信号，CLR是清零信号，Q和 nQ是两个输出。
地址转换器
地址转换器负责根据需求选中工作的单元，未选中的单元不工作。
传统的计算机中，每个地址对应一个单元。但是，分子计算的算法要求能够一次选中一
个或多个单元，所以需要一个不同以往的地址转换器。本系统中的地址变换器利用四值逻辑
的思想来实现。
四值逻辑有四种逻辑状态：F，0，1，*。假设有两个计算单元待选择，它们的地址片
选端分别为 CS0，CS1，则地址转换器输入F表示一个都不选中，0 表示选中单元 0，1 表
示选中单元 1，*表示选中单元 0和 1.
由于用电子的方式实现四值逻辑，所以在本系统中，四值逻辑的每一位用二进制的两位
来表示，分别为F —00， 0—01， 1—10，*—11，这两位可以看作高低两位，称作位 1和
位 0。
用一个规模为 16（
42 ）的并行存算阵列来举例，需要地址变换器输出 16个片选信号，
地址模块需要 2*4=8个输入信号。
对计算单元编号为从 0000到 1111。地址模块输入为 01_01_01_01时，按四值逻辑即为
0000，即选中单元 0000。地址模块输入为 11_01_11_01 时，按四值逻辑即为*0*0，即选中
-7-
单元 0000，0010，1000，1010。 若要选择单元 0111，则需使输入为 0111，即 01_10_10_10。
要选择单元 1*0*，则需使输入为 1*0*，即 10_11_01_11。
图 6. 16个功能单元的地址转换逻辑图
通过观察下面的地址转换逻辑图可知，要选中单元 0000 时，输入为*1_*1_*1_*1,不管
位 1取值为 0还是 1，只要所有位 0取值为 1即可，即
CS0=addr[6]&addr[4]&addr[2]&addr[0]，同理有
CS1=addr[6]&addr[4]&addr[2]&addr[1],
CS2=addr[6]&addr[4]&addr[3]&addr[0],
…
CS15=addr[7]&addr[5]&addr[3]&addr[1]
那么这个规模为 16（
42 ）的并行存算阵列对应的地址转换器，其结构（部分）如下图
所示：
图 7. 地址转换器(部分)
从上面的分析可以知道，规模为 n 的阵列，需要2n个片选信号来确定选中哪些单元，
由于使用了四值逻辑，地址转换器就需要一个 2n位的输入，然后将其转换成相应的2n位的
地址来选中相应单元。
本文中的系统是针对 10变量的 SAT问题的，其规模达到 1024，所以其地址转换器的输
入是 2*10=20位，输出是 1024个片选信号，实现逻辑和上面描述的规模为 16的类似，只是
规模相应扩大。其逻辑表达式如下所示：
CS[0] = in[18]&in[16]&in[14]&in[12]&in[10]&in[8]&in[6]&in[4]&in[2]&in[0];
…
CS[1022] = in[19]&in[17]&in[15]&in[13]&in[11]&in[9]&in[7]&in[5]&in[3]&in[0];
CS[1023] = in[19]&in[17]&in[15]&in[13]&in[11]&in[9]&in[7]&in[5]&in[3]&in[1];
数据发生器
-8-
这部分的实现和地址转换器非常相似，仍然用前面提到的规模为 16（
42 ）的并行存算
阵列来举例，分子计算的算法要求能够一次为所有的单元打入不同数据，如为 0000单元输
入 0000，0001单元输入 0001，…，1111单元输入 1111，我们可以得出，只需要把地址发生
器逻辑表达式右边的&换成连接即可。
Dout0={Din[6], Din[4], Din[2], Din[0]},
Dout1={Din[6], Din[4], Din[2], Din[1]},
...
Dout15={Din[7], Din[5], Din[3], Din[1]}
本文中实现的系统是针对 10变量的 SAT问题设计，不需要该部分，其写入功能直接由
读写系统完成。
读写系统
DNA 计算中，无法快速的从所有计算结果中找出符合要求的解，用传统计算机的串行
方法，在规模为 2n的存储单元中找到一个解的时间复杂度是 (2 )nO ，并且在找到一个结果
之后停机，如果存在多个解，则其他的解有不被找出的可能。
在基于 DNA计算的单片机并行处理系统中，所有的结果都存储在前文提到的并行处理
存算阵列中，读出可以采用二分法进行，可以大大降低时间复杂度，对于规模为 2n的存算
阵列，找到解的时间复杂度仅为 2(log )O n 。假设有 k个解，那么在找到一个解后，将其存
储在存算阵列之外的存储器中，然后将该解从存算阵列中删除，再重复进行二分查找和转存、
删除解的过程，直到存算阵列中没有解为止。这样就可以把所有的解都找到，并且时间复杂
度仅为 2( log )O k n 。
针对本文中实现的系统，将并行存算阵列中所有功能单元的输出，即图 5 中的 Q 端线
与,记为 out_Q；nQ端也线与，记为 out_nQ。这样就可以根据这两个线与的结果来判断目前
选中的单元中是否有解，
out_Q与 out_nQ的值 所表示的意义
00 表示选中单元中有解
01 表示选中单元中无解
10 表示选中的所有单元都是解
11 错误
表 3. out_Q与 out_nQ的值所表示的意义
控制器可以根据这个反馈值来判断是放弃这个分支或者继续选择下层分支来找解。
由于所选器件的原因，在实现“线与”这一逻辑功能的时候，只能通过“与”的方式来
实现，导致了一部分资源的浪费。这个问题可以通过选择 CPLD XC9500来解决，该芯片可
以实现“线与”功能。
读写系统中的写功能，是通过将图 5 中的 D 端连在一起实现，直接根据需要往所有的
功能单元中写数据。
3. 2 实例：10变量的3-SAT问题的解答
含有 12个变量的 3-SAT问题
f=(x1|x2|x3) & (x1|x2|~x3) & (x1|~x2|x3) & (x1|~x2|~x3) & (~x1|x2|x3) & (~x1|x2|~x3) &
(~x1|~x2|x3) & (~x1|~x2|~x4) & (~x3|x4|~x5) & (x4|x5|~x6) & (x5|x6|~x7) & (x6|x7|~x8) &
(~x1|x5|x9) & (~x2|x6|~x10})
具体步骤是：
1）生成所有解
-9-
在地址转换器的输入端输入 0xfffff，即选中所有功能单元，然后写入 1。
2）对每个子式删除“非解”
对某些功能单元置 0表示非解。
不满足子式(x1|x2|x3)的解为 x1x2..x10取值为 0,00*,***,***，*表示 x4~x10的取值与此
子式无关。那么，就需要在地址转换器的输入端输入 0x57fff，选中相应的功能单元，写入 0，
表示这些单元的地址是非解，即删除非解 0x57fff。
不满足子式(x1|x2|~x3)的解为 x1x2..x10 的取值为 0,01*,***,***，*表示 x4~x10 的取值
与此子式无关。需要在地址转换器的输入端输入 0x5bfff，选中相应的功能单元，写入 0，表
示这些单元的地址是非解即删除非解 0x5bfff。
依此类推，将所有子式都这样处理完毕之后，就将所有的非解删除了。
3）读出解
现在并行村算阵列中所有值为 1的单元地址，就是所求问题的解集。
地址转换器输入 0xfffff，选中所有单元，out_Q与 out_nQ 的值为 00，说明有解；选择
前一半分支，即输入 0x7ffff，out_Q与 out_nQ的值为 01，说明前一半没有解；选择后一半
分支，即输入 0xbffff，out_Q与 out_nQ的值为 01，说明后一半分支中有解⋯⋯依此类推，
找到一个解后。将其地址保存，然后将该单元置 0，即删除并行村算阵列中的这个解。然后
再次依照前面的方法查找，直到得到问题的全部解。
该问题的解只有一个，就是 0xa9559。
图 8. 找到最后解的阵列
3. 3 性能评价
从上面求解的过程可以看出，对于一个 n个变量 m个子式的 SAT问题，初始化需要 1
步，删除非解过程需要 m步，读出解的过程和解的个数有关，假使有 k个解，就需要 k(n+1)
步，时间复杂度是 (1 ( 1)) ( )O m k n O kn+ + + = ，是一个多项式值。如果用传统计算机来解
n个变量的 3-SAT问题，时间复杂度为 ( *2 )nO n 。也就是说，本系统将时间复杂度从指数
级降到了多项式级。虽然在时间复杂度降低的同时，牺牲了空间，功能单元的个数是 2n，
空间复杂度是 (2 )nO ，但是，一方面由于电子技术和集成电路技术的发展，使得硬件电路的
成本降低，另一方面，时间具有一维性是不可逆转的，所以这种以牺牲空间的方式换取时间
是值得的。
4．总结
本文尝试设计并实现了一个新的并行系统，该系统以 FPGA作为主体框架，单片机做为
控制器，参照 DNA 计算的模式，继承了 DNA 计算并行度高，运算速度快的优点，同时保
留了电子计算的精确性，电子电路价格低廉等优点。在实验室已有的系统基础上，将控制器
部分从 FPGA中剥离出来由单片机实现，进一步扩大了系统规模，可以解决 10变量的 SAT
问题，并且增加了诸如汇编器一类的小工具，方便对系统的操作。只要通过选取合适的器件，
可以进一步扩大系统规模。
目前，该系统的应用范围比较有限，但是通过对算法的改进，相信可以进一步扩大其应
用范围。
-10-
参考文献
[1] Adleman L M． Molecular computation of solutions to combination problems[J]．Science， 1944， 266：
1021-1023．
[2] 许进，张雷．DNA计算机原理、进展及难点(I)：生物计算系统及其在图论中的应用[J]．计算机学报，
2003，26(1) ．
[3] 廉明欢．基于 IC的 DNA计算模型的设计[D]．北京：北京邮电大学，2007．
[4] 高琳，许进，张军英．DNA计算的研究进展与展望[J]．电子学报，2001，29：975-977．
[5] 李人厚，余文．关于 DNA计算的基本原理与探讨[J]．计算机学报，2001，24(9) ．
Parallel System Based On DNA Computation
Yang Rui
Computer Architecture Centre, School of Computer, Beijing University of Posts and
Tele-Communication (100044)
Abstract
DNA Computer is a choice of new generation computer because of its advantages such as high
parallelism, high-speed computing, huge store capacity. But it is hard to control and distinguish DNA
molecule, there is no practical DNA computer now. On the other hand, the cost of electric circuit is
becoming lower because of the integrated circuit technology developing. The paper gives an idea about
parallel system, which can combine the advantages of DNA computing and integrated circuit. Improves
the system designed in lab, implement the main system frame on FPGA, separate controller from
FPGA and use a MCU to control system, enlarge the scale of system, follow the steps of DNA
computing, realize a address transform of 4-value logic, solve a 10-variable instance of 3-SAT problem.
Keywords: DNA Computation, Parallel System, FPGA, MCU, SAT Problem
