2024年4月17日发(作者：)

维普资讯

第２６卷　

２００６年６月　

文章编号：１００１—９０８１（２００６）０６Ｚ一０２６１—０３　

计算机应用　

Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　

Ｖｏ１．２６　

Ｊｕｎｅ　２００６　

嵌入式Ｌｉｎｕｘ交叉开发环境　

康涌泉，桑楠，邹楚雄，邓竹莎　

（电子科技大学计算机科学与工程学院，四川成都６１００５４）　

（ｄｉ—ｓｈｕｉ＠ｔｏｍ．ｃｏｒｎ）　

摘要：对嵌入式软件交叉开发技术进行探讨和研究。利用开源软件在Ｗｉｎｄｏｗｓ操作系统下，构　

建了一个嵌入式Ｌｉｎｕｘ的交叉开发环境，开发了ｂｕｓｙｂｏｘ等应用程序，为“龙芯ｇｓ３２ｉ”开发板搭建了一　

个嵌入式Ｌｉｎｕｘ的运行平台。　

关键词：嵌入式开发环境；龙芯ｇｓ３２ｉ；Ｃｙｇｗｉｎ；ｇｏｄｓｏｎ—ｈｎｕｘ；ＢｕｓｙｂＯＸ　

中图分类号：ＴＰ３１１．５２　文献标识码：Ａ　

０　引言　

随着嵌入式Ｌｉｎｕｘ应用的日益扩展，其开发环境的研究　

也越来越受到人们的重视。国内外许多公司都在致力于嵌入　

式Ｌｉｎｕｘ交叉开发工具和集成开发环境的研究，并推出了自　

己的产品，如：ＴｉｍｅＳｙｓ的ＴｉｍｅＳｔｏｒｍ　Ｔｏｏｌｓ、ＬｙｎｕｘＷｏｒｋｓ的　

ＬｙｎｕｘＷｏｒｋｓ。红旗的ＣｏｎｔｒｏＬｉｎｕｘ　ＥＤＫ、英培特公司的Ｅｍｂｅｓｔ　

２　嵌入式Ｌｉｎｕｘ交叉开发环境　

嵌入式Ｌｉｎｕｘ交叉开发技术方面的研究，近年来取得了　

很大的进步，尤其是集成开发环境的应用，大大简化了用户对　

内核和应用程序的开发流程。如ＴｉｍｅＳｙｓ公司的ＴｉｍｅＳｔｏｒｍ　

Ｔｏｏｌｓ为用户提供了友好的人机交互界面，并把交叉开发过程　

中要用到的工具都集成到一个应用环境中，帮助用户方便的　

ＩＤＥ等。但出于商业利益的考虑，这些产品一般都未开放源　

码，特别是在Ｗｉｎｄｏｗｓ环境下如何实现面向嵌入式Ｌｉｎｕｘ应　

用的交叉开发，更是作为核心技术加以保护。　

“龙芯ｇｓ３２ｉ”是由中科院计算机技术研究所自主研发的　

一

选择交叉编译程序，确定程序的安装过程和安装位置等。　

一

般而言，交叉开发环境的搭建过程的核心，即交叉编译　

工具、汇编工具、连接工具、调试工具的建立，大体上都的遵循　

图２所示流程。　

编译调试工具ｇｄｂ　

款高性能、低功耗ＳＯＣ模式ＣＰＵ，可运行ＭＩＰＳ３２指令系　

统，支持３２位Ｌｉｎｕｘ操作系统和ｘ－ｗｉｎｄｏｗｓ视窗系统。在市　

场广阔的嵌入式应用领域，龙芯系列处理器必定会得到越来　

越广泛的应用。但是，龙芯的技术资料基本上都未公开，针对　

龙芯的嵌入式应用开发工具也比较缺乏，给用户的开发应用　

带来了很大的困难。　

ｌ　

Ｉ　

重新编译完整的编译工具ｇｃｃ　

＋　

编译该平台的ｇｌｉｂｃ库　ｌ　

＋　

编译自举的编译工具ｇｃｃ　

ｌ　

｝　

Ｉ　生成汇编器、连接器、库处理工具等　

本文在分析嵌入式软件交叉开发原理的基础上，介绍了　

如何在Ｗｉｎｄｏｗｓ操作系统下利用开源软件、针对龙芯处理器　

实现嵌入式Ｌｉｎｕｘ应用软件的交叉开发环境，提出了一个比　

较完整的解决方案，并成功地为“龙芯ｇｓ３２ｉ”开发板搭建了一　

个嵌人式应用软件开发环境。　

’　＋　

Ｉ准备硬件环境头文件Ｉ　ｌＰＣ环境工具和库等　

图２交叉开发环境建立流程　

３　ｇｏｄｓｏｎ—ｌｉｎｕｘ交叉开发环境　

ｇｏｄｓｏｎ－ｌｌｎｕｘ是利用Ｃｙｇｗｉｎ构造的一个嵌入式Ｌｉｎｕｘ开　

发环境，分成宿主端和目标端两部分。　

应用程序　

１　嵌入式软件的交叉开发　

宿主机：ＰＣ　

编译器　

汇编器　

连接器　

调试工具　

目标机：嵌入式　

系统平台　

】　

Ｉ　

Ｆｌａｓｈ　

ＤＯＣ　

ｌ　

ｌ　

Ｉ　

虚￣ＡＬｉｎｕｘ操作系统　

ｇｏｄｓｏｎ－ｌｉｎｕｘ　

调试代理　

图１交叉开发环境示意　

配置工具、工程工具、调试工具　

汇编工具、连接工具　

如图１所示，嵌入式软件的交叉开发环境通常由“宿主　

Ｃｙｇｗｉｎ　Ｉ　

Ｉ　

ｌ动态链接库　

｝　

机”和“目标机”两部分构成。应用程序在宿主机上编辑、编　

译，下载到目标机上运行；对应用程序的调试是通过运行于目　

标机的调试代理程序（或仿真器）与宿主机上运行的调式工　

具一起协同来控制其调试过程。　

Ｗｉｎｄｏｗｓ￣作系统　

图３交叉开发环境宿主端结构　

宿主端结构如图３所示。其中，Ｃｙｇｗｉｎ是ＲｅｄＨａｔ公司提　

供的一个开源集成环境，它是Ｗｉｎｄｏｗｓ到Ｌｉｎｕｘ的一种中介：　

收稿日期：２００５—１Ｏ一０８：修订日期：２００５—１２一Ｏ８　基金项目：国家８６３计划资助项目（Ｍ０７０１０６０１０３ＡＡＩＺ２２１０）　

作者简介：康涌泉（１９７８一），男，Ｉ￣Ｊｔｌ安岳人，硕士研究生，主要研究方向：嵌入式Ｌｉｎｕｘ技术、Ｌｉｎｕｘ　ＢＳＰ技术；　桑楠（１９６４一），男，四川成　

都人，副教授，博士研究生，主要研究方向：嵌入式实时系统、嵌入式软件工程；邹楚雄（１９７６一），男，湖南新宁人，硕士研究生，主要研究方向：　

嵌入式交叉调试工具；邓竹莎（１９８２一），女，Ｉ￣Ｊ　ｒｌ康定人，硕士研究生，主要研究方向：嵌入式实时系统．　

维普资讯

２６２　计算机应用　２００６．年　

提供类Ｌｉｎｕｘ的开发指令，让所有ＩＡｎｕｘ的开发指令在　

现在，有ｇｏｄｓｏｎ－ｌｉｎｕｘ工具链，有适用于ｇｓ３２ｉ体系的ｃ　

库，该回过头去重新编译一个完整的ｇｃｃ了，先运行ｍａｋｅ　

ｃｌｅａｎ清除掉编译Ｂｏｏｔｓｔｒａｐ　ｇｅｅ时留下的痕迹，再重新配置如　

下：　

／ｃｏｎｆｉｕｒｅ一ｇ一ｐｒｅｆｉｘ＝／ｕｓｒ／ｌｏｃａｌ／ｃｒｏｓｓｄｃｖ一一ｔａｒｇｅｔ　ｇｏｄｓｏｎ－ｌｉｎｕｘ一一　

ｅｎａｂｌｅ－ｌｎｇａｕａｇｅｓ＝Ｃ．Ｃ＋＋　

Ｗｉｎｄｏｗｓ平台可以得到识别和执行，但编译生成的最终结果　

只能在Ｗｉｎｄｏｗｓ操作系统下运行。　

基于Ｃｙｇｗｉｎ，可以集成适应于“龙芯ｇｓ３２ｉ”平台的交叉开　

发工具链，包括配置工具、工程工具、编译工具、调试工具和Ｃ　

函数库等，共同构成了一个基于Ｗｉｎｄｏｗｓ的虚拟Ｌｉｎｕｘ交叉　

开发环境宿主端。　

然后运行ｍａｋｅ＆＆ｍａｋｅ　ｉｓｔｎａｌｌ完成ｇｃｃ的编译安装。至　

此，已经成功构建起一个适用于龙芯“ｇｓ３２ｉ”的交叉编译器。　

４．２交叉调试器　

交叉开发的目标机端构造如图４所示。通过在目标机上　

运行调试代理程序的方式，将目标机上程序的运行状态发送　

到宿主机上，从而实现对应用程序的控制和调试工作。本系　

程序的调试是检查程序正确性、可靠性、稳定性的重要手　

统中采用了ｇｄｂ发行包中的调试代理程序ｇｄｂｓｅｒｖｅｒ。　

｝　目标机　

ｆ　磊　厂＿面醺孬］厂　丽　

ｌ　Ｉ令程序ｌｌ　ｇｄｂｓｅｒｖｅｒ　Ｉ　

；　＋　Ｉ　

Ｉ　嵌入式Ｌｉｎｕｘ内核驱动程序　Ｉ　

｝　

ｌ　龙芯开发板　Ｉ　

图４交叉开发环境目标端结构　

４重要组成模块的设计说明　

４．１交叉编译器　

交叉编译器是整个交叉开发环境的核心模块，所有应用　

程序的编译都必须由该模块完成才能在特定的硬件平台运　

行。　

在本系统中，需要一个工具能编译适应于龙芯体系的ｃ　

函数库，然后再利用这个ｃ库系统完成对ｇｅｅ的编译，这个工　

具被称作ｂｏｏｔｓｔｒａｐ　ｇｃｃ，如图５所示。　

ｌ　准备ｇｓ３２ｉ环境头文件　Ｉ　

　｝Ｉ　

　｝Ｉ　编ｉ￣ｂｉｎｕｔｉｌｓ　ｌ　

Ｉ　

ｌ编译自举的（ｂｏｏｔｓｔｒａｐ）ｇｅｅ　Ｉ　

ｂｏｏｔｓｔｒａｐ　ｇｅｅ工具已经可以编译内核了　

Ｉ　

Ｉ　编译ｇｓ３２ｉ的ｇｌｉｂｃ　Ｉ　

Ｉ　

Ｉ　重新编译完整的ｇｃｃ　Ｉ　

图５交叉编译器构建过程　

ｂｏｏｔｓｒｔａｐ　ｇｅｅ的编译配置过程如下：　

．

／ｃｏｎｆｉｇｕｒｅ—ｐｒｅｆｉｘ＝／ｕｓｒ／ｌｏｃａｌ／ｃｍｓｓｄｃｖ－－ｗｉｔｈ—ｎｃｗｌｉｂ一－ｔａｒｇｅｔ＝　

ｇｏｄｓｏｎ—ｌｉｎｕｘ－－ｅｎａｂｌｅ—ｌａｎｇｕａｇｅｓ＝Ｃ—ｄｉｓａｂｌｅ—ｔｈｒｅａｄｓ一－ｄｉｓａｂｌｅ．　

ｓｈａｒｅｄ　

配置完成后运行ｍａｋｅ＆＆ｍａｋｅ　ｉｎｓｔａｌｌ即可完成ｂｏｏｔｓｒｔａｐ　

ｇｅｅ工具的编译和安装。ｂｏｏｔｓｒｔａｐ　ｇｅｅ运行时不依赖于ｃ库，　

可以直接编译Ｌｉｎｕｘ的应用程序或ｃ库函数，但因其支持的　

函数有限，有些程序可能会编译不成功。现在，利用ｂｏｏｔｓｒｔａｐ　

ｇｃｃ工具来编译ＧＮＵ的ｃ库ｇｌｉｂｃ，这里要用到ｇｏｄｓｏｎ．１ｉｎｕｘ工　

具链提供的工具，在编译之前将工具链的路径加入到ＰＡＴＨ　

中，运行：　

ｅｘｐｏｒｔ　ＰＡＴＨ＝／ｕｓｒ／ｌｏｃａｌ／ｃｍｓｓｄｅｖ／ｂｉｎ：￥ＰＡＴＨ　

配置过程如下：　

ＣＣ＝ｓｏｄ￣ｏｎ—ｌｉｎｕｘ－ｇｅｅ　ＲＡＮＬＩＢ＝ｇｏｄｓｏｎ－ｌｉｎｕｘ．ｒａｎｌｉｂ　ＡＲ：画ｏｄｓ０ｎ—　

ｌｉｎｕｘ－ａｒ．／ｃｏｎｆｉｇｕｒｅ—・ｐｒｅｆｉｘ＝／ｕｓｒ／ｌｏｃａｌ／ｃｒｏｓｓｄｅｖ／ｇｏｄｓｏｎ．１ｉｎｕｘ　

－－

ｅｎａｂｌｅ—ａｄｄ－ｏｎｓ＝ｌｉｎｕｘｔｈｒｃａｄｓ　ｈｏｓｔ　ｇｏｄｓｏｎ－ｌｉｎｕｘ　

然后运行ｍａｋｅ＆＆ｍａｋｅ　ｉｓｎｔａｌｌ完成　ｂｃ的编译和安装。　

段，也是应用程序开发必不可少的组成部分。利用刚才生成　

的交叉编译器来构建交叉调试器，这里采用ＧＮＵ的Ｇｄｂ工具　

作为宿主机上对应用程序调试的工具。其配置如下：　

ＣＣ　ｇｏｄｓｏｎ—ｌｉｎｕｘ—ｇｅｅ．／ｃｏｎｆｉｇｕｒｅ　

一一

ｔａｒｇｅｔ　ｇｏｄｓｏｎ－ｌｉｎｕｘ－－ｐｍｆＬＸ＝／ｕｓｒ／ｌｏｃａｌ／ｃｍｓｓｄｅｖ　

然后运行ｍａｋｅ＆＆ｍａｋｅ　ｉｓｎｔａｌｌ完成ｇｄｂ的编译安装，在　

宿主机上就可以用这个交叉调试工具来调试应用程序。　

４．３调试代理　

应用程序运行于龙芯目标平台，作为资源受限的嵌入式　

系统，这里选择使用调试代理程序来实现对应用程序的调试。　

ｇｄｂｓｅｒｖｅｒ是ｇｄｂ发行包中的一个应用程序，为应用于“ｇｓ３２ｉ”　

目标板，需要进行合理的配置和编译。切换到ｇｄｂ－６．０／ｇｄ￣　

ｇｄｂｓｅｒｖｅｒ／目录下，输入如下配置命令：　

．

／ｃｏｎｆｉｕｇｒｅ　ｈｏｓｔ　ｉ６８６一ｐｃ—ｌｉｎｕｘ－ｇｎｕ—ｔａｒｇｅｔ　Ｓｏｄ￣ｏｎ—ｌｉｎｕｘ　

然后运行ｍａｋｅ命令编译生成最终可执行文件ｇｄｂｓｅｒｖｅｒ，　

将其拷贝到目标机平台／ｕｓｒ／ｓｂｉｎ目录下，作为系统用户应用　

程序。　

５　系统实现　

实践中选择一台ＰＣ机作为宿主机，龙芯“ｇｓ３２ｉ”开发板　

作为目标机。采用上述方法，可以构造基于龙芯“ｇｓ３２ｉ”的嵌　

入式开发环境。　

但是，嵌入式系统的目标机往往是一个裸机，无法直接运　

行嵌入式Ｌｉｎｕｘ，为此，本系统利用Ｂｕｓｙｂｏｘ为Ｌｉｎｕｘ系统构造　

一

个可运行环境。具体的配置生成过程描述如下：　

运行ｍａｋｅ　ｍｅｎｕｃｏｎｆｉｇ进行配置，设置ｂｕｉｌｄ　ｏｐｔｉｏｎｓ选项　

中ｃｒｏｓｓ　ｃｏｍｐｉｌｅｒ　ｐｒｅｆｉｘ￣＇Ｊ／ｕｓｒ／ｌｏｃａｌ／ｃｍｓｓｄｅｖ／ｂｉｎ／ｇｏｄｓｏｎ．　

１ｉｎｕｘ－，设置ｉｓｎｔａｌｌａｔｉｏｎ　ｐｒｅｆｉｘ为／ｍｎｔ／ｈｄｂ，选择系统需要的　

ｓｈｅｌｌ以及各种小应用程序，完毕以后保存配置文件并退出，　

运行ｍａｋｅ命令就得到编译好的ｂｕｓｙｂｏｘ。　

为硬盘创建一个ｌｉｎｕｘ　ｅｘｔ２分区，并ｍｏｕｎｔ到／ｍｎｔ／ｈｄｂ。　

安装ｂｕｓｙｂｏｘ时就在硬盘分区中创建了／ｂｉｎ和／ｓｂｉｎ目录和应　

用程序，再根据系统需要创建系统目录、设备文件节点等，创　

建一个／ｂｋ目录，将之前交叉编译得到的适应于龙芯“ｇｓ３２ｉ”　

目标板的内核拷贝到该目录下，拷贝系统所需应用程序及动　

态连接库到相应目录，同时修￣／ｅｔｃ／ｆｓｔａｂ、／ｅｔｃ／ｉｎｉｔｔａｂ、／ｅｔｃ／　

ｉｎｉｔ．ｄ／ｒｃＳ脚本。至此，整个目标系统就可以直接从硬盘引　

导。　

至此，整个基于龙芯开发板的Ｌｉｎｕｘ系统交叉开发环境　

已构造完成，下面利用该环境实现一个专为嵌入式环境设计　

的图形用户界面——ＭｉＩｌｉｇＩｌｉ库。其源码可以从ｈｔｔｐ：／／ｗｗｗ．　

ｍｉｎｉｇｕｉ．ｃｏｎｒ／ｄｏｗｎｌｏａｄ下载到，解开后会形成三个目录　

“ｌｉｂｍｉｎｉｇｕｉ一１．３．０”、“ｍｉｎｉｇｕｉ．ｒｅｓ．１

．

３．０”、“ｍｄｅ．１．３．０”。　

Ｍｉｎｉｇｕｉ有两种运行模式，一种是ｔｈｒｅａｄ模式，另一种是ｌｉｔｅ模　

维普资讯

６月　康涌泉等：嵌入式Ｌｉｎｕｘ交叉开发环境　２６３　

式，实验中选择的是ｌｉｔｅ模式（关于Ｍｉｎｉｇｕｉ的更多信息，请查　

阅其手册）。设置环境变量ＰＡＴＨ如下：　

ＰＡＴＨ＝／ｕｓｒ／ｇｏｄｓｅｎ—ｌｉｎｕｘ／ｂｉｎ：ＳＰＡＴＨ　

还未在该系统上实现图形窗口，只能在虚拟终端上进行操作，　

给应用开发人员的使用带来一些不便。这些问题将会在未来　

的研究中逐步解决，使交叉开发环境更加完善，并在应用领域　

得到更大的扩展。　

参考文献：　

ｆｔｌ　ＷＩＮ—ＢＩＮＳＥＥ，ＰＡＯ—ＡＮＮ　ＨＳＩＵＮＧ，ＴＲＯＮＧ・ＹＥＮＬＥＥ，ｅｔｏ２．　

Ｓｏｆｔｗａｒｅ　ｐｌａｔｆｏｒｍ　ｆｏｒ　ｅｍｂｅｄｄｅｄ　ｓｏｆｔｗａｒｅ　ｄｅｖｅｌｏｐｍｅｎｔ【Ａ】，Ｒｅａｌ—　

Ｔｉｍｅ　ａｎｄ　Ｅｍｂｅｄｄｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，９ｔｈ　Ｉｎｔｅｒ－　

首先编译Ｍｉｎｉｇｕｉ的函数库ｌｉｂｍｉｎｉｇｕｉ，进入ｌｉｂｍｉｎｉｇｕｉ一１．　

３．０目录进行配置：　

／ｃｏｎｆｉｇｕｒｅ　ｈｏｓｔ　ｉ６８６一ｐｅ—ｌｉｎｕｘ—ｇｎｕ一一ｅｎａｂｌｅ—ｌｉｔｅ　

配置完成后输入命令ｍａｋｅ　ｉｎｓｔａｌｌ，系统将开始编译和生　

成ｍｉｎｉｇｕｉ的动态和静态库文件，并将生成的库文件安装到／　

ｍｒ／ｌｏｃａｌ／ｌｉｂ目录下，相应的头文件将会安装到／ｕｓｒ／ｌｃａｌｏ／　

ｉｎｃｌｕｄｅ／ｍｉｎｉｇｕｉ目录下，然后进入ｍｉｎｉｇｕｉ－ｒｅｓ－１．３．０目录安装　

ｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ，ＲＴＣＳＡ　２００３【Ｃ】，Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－　

Ｖｅｒｌａｇ．２００４．５４５—５７．　

资源文件，至此，Ｍｉｍｇｕｉ图形开发环境就建立起来了，利用该　

环境，编译ｍｄｅ．１．３．０中的演示程序，编译完成后，该演示程　

序在龙芯“ｇｓ３２ｉ”系统平台上成功运行起来。　

【２】ＬＥＨＲＢＡＵＭ　Ｊ，ＷＥＩＮＢＥＲＧ　Ｗ．Ｃｒｏｓｓ—ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｅｍｂｅｄｄｅｄ　

Ｌｉｎｕｘ　ｐｒｏｇｒａｍｓ　ｏｎ　ｗｉｎｄｏｗｓ・ｂａｓｅｄ　ｈｏｓｔ　ｃｏｍｐｕｔｅｒｓ【Ｊ】，Ｅｌｅｋｔｏｎｉｒｋ，　

２００３，５２（１６）：４５—９．　

【３】　ＳＥＵＮＧＷＯＯ　ＳＯＮ，ＣＨＡＥＤＥＯＫ　ＬＩＭ．ＨＥＵＮＧ－ＮＡＭ　ＫＩＭ．Ｄｅｂｕｇ－　

６结语　

在嵌入式软件系统设计中，交叉开发环境的设计至关重　

要，本文通过对嵌入式Ｌｉｎｕｘ交叉开发平台技术的探讨和研　

究，利用开源软件构建了一个嵌入式Ｌｉｎｕｘ的交叉开发环境，　

并成功地在龙芯“ｇｓ３２ｉ”系统上实现了一个嵌入式Ｌｉｎｕｘ运行　

平台，在此基础上，可以构建更丰富的应用，目前已经完成　

ｗｅｂ服务器、ＳＳＨ服务程序、Ｍｉ￣ｉｓｕｉ库等。　

当然这个交叉开发平台还有很多不足，其编程、编译、链　

ｇｉｎｇ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｒｅｍｏｔｅ　ｃｒ０ｓ８　ｄｅｖｅｌｏｐｍｅｎｔ　ｅｎｖｉｒｏｎｍｅｎｔ【Ａ】，Ｐｒｏｃｅｅｄ・　

ｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｅｖｅｎｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅａｌ—Ｔｉｍｅ　Ｓｙｓｔｅｍｓ　

ｎｄ　Ａｐｐｌａｉｃａｔｉｏｎｓ（ＲＴＣＳＡ＇００）【Ｃ】．２ＯＯＯ．　

【４】　陈滔，李志刚．刘执远，等．ＣＣ—Ｌｉｎｕｘ集成开发环境的设计与实现　

【Ｊ】．计算机工程与应用，２００１，３７（２３）．　

【５】　刘执远．嵌入式Ｌｉｎｕｘ集成开发环境【Ｍ】．西安：西北工业大学．　

２ｏ０１．　

【６】何家胜．龙芯开发板的软件构建【Ｚ】。２００４．　

【７】　Ｂｕｓｙｂｏｘ：Ｔｈｅ　Ｓｗｉｓ　ａｒｍｙ　ｋｎｉｆｅ　ｏｆ　ｅｍｂｅｄｄｅｄ　ｌｉｎｕｘ【ＥＢ／ＯＬ】．ｈｔ－　

ｔｐ：／／ｂｕｓｙｂｏｘ．ｎｅｔ／ａｂｏｕｔ．ｈｔｍ１．２００５一ｌＯ．　

接库、调试工具等相对独立，没有一个统一的操作窗口；目前　

（上接第２５４页）　

结果反应不出基于外存的索引结构的性能特点，因此我们只　

使用冷结果作为评价算法性能的依据：每次查询进行之后，都　

有相应的清理内存的动作。　

３．３结果分析　

表１实验结果分析　

４　结语　

针对ＮＢ—ｔｒｅｅ只存储对象的欧氏距离而忽略位置信息的　

缺点，提出了Ｎｅｗ－ＮＢ—ｔｒｅｅ索引结构。Ｎｅｗ－ＮＢ—ｔｒｅｅ主要是修　

改了ＮＢ－ｔｒｅｅ叶子节点的结构，增加了独立于维数的角度信　

息，通过较小的存储空间和代价不大的计算，在完成原有的过　

滤功能外，进行了第二级过滤，减少了Ｉ／Ｏ次数，提高了算法　

的效率。实验数据证明了算法的有效性。　

参考文献：　

【１　１　ＧＡＥＤＥ　Ｖ，ＧＵＮＴＨＥＲ　Ｏ．Ｍｕｌｉｔｄｉｍｅｎｓｉｏｎａｌ　Ａｃｃｅｓｓ　Ｍｅｔｈｏｄｓ【Ｊ】．　

　

查询半径０．０４查询半径０．０６查询半径０．０８　

查询半径０．１

旧算法新算法旧算法新算法旧算法新算法　旧算法新算法　

２２ｌ６　ｌ　６３６　２５６ｏ　ｌ　９６０　２８９０　２４０４　

４５６３　４０９７　

ｌ　６５４　

ｌ９８０　

２６３１　

ｌ　ｌ３６　

ｌ４２３　

ｌ９６２　

２２３４　

ｌ　３９２　

ｌ７４８　

２２３４　

２５６９　

３４６１　

ｌ　８２０　

２０６４　

２７９８　

３６１０　２９３１　

３６２１　３ｌ９Ｏ　

１７６７　３ｌ１２　２２２６　５６９８　４８４６　

ＡＣＭ　Ｃｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ，１９９８，３０（２），１７０—２３１．　

９６６　

ｌ　５８９　

６６５　ｌ　２６８　９８９　ｌ　６５７　ｌ４８８　２６４５　２３５２　

２２３４　

３２３４　

【２１　ＷＥＢＥＲ　Ｒ，ＳＣＨＥＫ　Ｈ－Ｊ，ＢＬＯＴ　Ｓ．Ａ　Ｑｕａｎｔｉｔａｔｉｖｅ　ＡｎＭｙｓｉｓ　ａｎｄ　Ｐｅｒ－　

ｆｏｒｍａｎｃｅ　ｓｔｕｄｙ　ｆｏｒ　Ｓｉｍｉｌａｒｉｔｙ—ｓｅａｒｃｈ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌ　

ｌ０６４　２３ｌ１　ｌ　７２０　２８８６　２５３０　

２６４ｌ　

２１３６　

ｌ　５８９　

２ｌ１４　

ｌ６６２　２５９４　２ｏ０３　

９３４　ｌ　８９８　

３ｌ５２　２５４６　

３８４５　

ｌ　３２０　２ｌ２３　ｌ６５４　

２９６４　

２３８６　３１５６　

３６７９　

２３４６　

２６９１　

３ｌ６ｏ　

Ｓｐａｃｅｓ［ＡＩ．Ｉｎ　２４ｔｈ　Ｉｎｔ．Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｄａｔａｂａｓｅｓ　

ｌ４６３　２４８０　２Ｏ８４　２６９８　

（ＶＬＤＢ）【Ｃ１．Ｎｅｗ　Ｙｏｒｋ，１９９８．１９４—２９５．　

［３１　ＦＯＮＳＥＣＡ　ＭＪ，ＪＯＲＧＥ　Ｊ．Ｉｎｄｅｘｉｎｇ　Ｈｉｓｈ・Ｄｉｍｅｎｓｉｏｎａｌ　Ｄａｔａ　ｆｏｒ　Ｃｏｎ－　

ｔｅｎｔ—Ｂａｓｅｄ　Ｒｅｔｒｉｅｖａｌ　ｉｎ　Ｄａｔａｂａｓｅｓ【ＡＩ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　

２３６５　ｌ　５３８　３ｌ２Ｏ　２３３２　３５６１　２７３３　

在磁盘进行一次Ｉ／０的时间里，一台典型的机器能执行　

百万条的指令　］，因此Ｉ／０操作所用的时间是算法所用时间　

的近似值，是影响索引算法效率的主要因素。在实验中以过　

滤后的对象数量作为Ｉ／０次数比较的量度。这里采用的检索　

效率提高程度的计算公式为：　

８ｔＭｎｔｅｍａｆｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ　ｆｏｒ　Ａｄｖａｎｃｅｄ　Ａｐ－　

ｐｌｉａｔｃｉｏｎｓ［ＣＩ．Ｋｙｏｔｏ，Ｊａｐａｎ，２００３．２６７—２７４．　

［４１　ＣＨＡ　ＧＨ，ＺＨＵ　ＸＭ，ＰＥＴＫＯＶＩＥ　Ｄ．Ａｎ　Ｆ－，￣ｃｉｅｎｔ　Ｉｎｄｅｘｉｎｇ　Ｍｅｔｈｏｄ　ｏｒ　ｆ

Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ　Ｓｅａｒｃｈｅｓ　ｉｎ　Ｈｉｓｈ—Ｄｉｍｅｎｓｉｏｎａｌ　Ｉｍａｇｅ　Ｄａｔａｂａｓｅｓ　

【Ｊ１．ＩＥＥＥ，２００２，４（１）：７６—８７．　

【５１　ＦＩＬＨＯ　ＲＦＳ，ＴＲＡＩＮＡＡ，ＴＲＡＩＮＡ　Ｃ　ＪＲ，ｅｔ　ｏ２．Ｓｉｍｉｌａｒｉｔｙ　Ｓｅａｒｃｈ　

ｉｔｗｈｏｕｔ　Ｔｅａｒｓ：ｔｈｅ　ＯＭＮＩ—Ｆａｍｉｌｙ　ｏｆ　Ａｌｌ—Ｐｕｒｐｏｓｅ　Ａｃｃｅｓｓ　Ｍｅｔｈｏｄｓ　

（　—ｏｌｄｎｕ　ｍｉ　－ｎｅｗｎｕｍｉ）／Ⅳ　

其中，ｏ／ｄｎｕｍ，　表示第　次旧算法过滤后的返回的数据量，　

ｎｅｗｎｕ／Ｙ／，　表示第ｉ次新算法过滤后的返回的数据量，Ⅳ表示检　

【ＡＩ．１７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ［Ｃ】．Ｈｅｉ—　

ｄｅｌｂｅｒｇ，Ｇｅｒｍａｎｙ，２００１．６２３—６３０．　

［６１　ＬＩ　Ｃ，ＣＨＡＮＧ　Ｅ，ＧＡＲＣＩＡ—ＭＯＬＩＮＡ　Ｈ，ｅｔ　ａ１．Ｃｌｕｓｔｅｒｉｎｇ　ｏｒ　ｆＡｐｐｒｏｘｉ．　

ｍａｔｅ　Ｓｉｍｉｌａｒｉｙ　ｔＳｅａｒｃｈ　ｉｎ　Ｈｉ　ｓｈ—ｄｉｍｅｎｓｉｏｎａｌ　Ｓｐａｃｅｓ［Ｊ１．ＩＥＥＥ　Ｔｒａｍ—　

索的次数。按着这种计算方法得到４种情况的检索效率的提　

高率分别为：３０．８％，２１％，１６．２％，１４．２％．从实验结果可　

以看出，当查询半径较小时，索引结构的效率提高较大。　

ａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｄｇｅ　ａｅｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００２，１４（４）：７９２—　

８０８．