基于复杂曲线表示的切比雪夫多项式拟合并行算法

第。７卷第６期上海交通大学学报

Ｖ０１．钾Ｎ¨－６

＝＝＝＝＝＝＝＝＝＝＝２＝＝＝＝；＝＝２＝＝＝＝＝＝＝＝＝＝；＝＝＝＝＝ｚ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝；＝＝＝＝＝＝＝＝＝＝＝；；；＝＝ｚ＝＝！＝＝＝＝＝＝＝＝＝＝＝＝＝＝ｋ＝２２２２２＝；＝＝ｆ＝！＝＝＝＝＝＝＝＝＝一一一

２０（日年６月

Ｊ（）ＵＲＮＡＬＯＦＳＨＡＮ（；ＨＡＴＪＩＡｏＴｏＮＧＵＮｌＶＥＲＳｌＴＹ

Ｊ…１

２…嵋

文章编号：１００６

２４６７（２００３）０６一０９０６一ｏｄ

基于复杂曲线表示的切比雪夫多项式拟合并行算法

邓倩妮１，

陈

笠２，

陆鑫达１，

何赢潮１

（１．１海交通大学计算机科学与工程系，上海２０。０３０；２．上海交通大学机械与动力工程学院，ｒ海２０００３０）

摘

要：骨科临床造型系统中进行假体再造时，要对ＣＴ片上的原始点采用数学逼近法进行优化

处理．常用的数学逼近法中切比雪夫多项式拟和法误差较小，对此，提出一种基于复杂曲线表示的切比雪夫多项式拟合并行算法．并采用两种】ａｖａ方案实现并行程序．实验结果表明，与一般的切比雪夫多项式拟舍串行算法相比，基于复杂曲线表示的切比雪夫多项式拟合并行算法保持了较高的计算精度，并获得了显著的加速比．

关键词：并行计算；数据拟合；切比雪夫多项式；多线程；Ｊａｖａ远程方法调用

中圈分类号：ＴＰ

３３８．６

文献标识码：Ａ

ＣｈｅｂｙｓｈｅＶＭｕＩｔｉｎｏｍｉａｌＡｐｐｒｏｘｉｍａｔｉｏｎＰａｒａ¨ｅｌＡ１９０ｒｌｔｈｍ

Ｂａｓｅｄ

０ｎ

ＣＯｍｐｌｅｘＣｕｒＶｅＲｅｐｒｅｓｅｎｔａｔｉｏｎ

ＤＥＮＧＱｊａｎ—ｍｔ，ＣＨＥＮＬ１２、￡ＵＸｔｎｃｉ０，ＨＥＹ１ｎｇｃｈａｏｊ

（１

Ｄｅｐｔ．ｏｆＣ。ｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｅｎｇ．，Ｓｈａ“ｇｈａｌＪｉａ。ｔ。“ｇｕｎｉｖ．，Ｓｈａ“ｇｈａｉ２０００３０，ｃｈ¨１ａ２．ｓｃｈｏｏｌ。ｆＭｅｃｈａｎｉｃａｌ

Ｅｎｇ．，ｓｈａｎｇｈａｉＪｉａｏｔｏｎｇｕｎｉｖ．，ｓｈａ“ｇｈａｉ２０００３０，ｃｈｌｎａ）

Ａｂｓｔｒａｃｔ：１ｎｔｈｅｐｒｏｃｅｓｓｏｆｒｅ—ｓｃｕｌｐｔｉｎｇａ九ｍｃｉａｌｂｏｎｅｉｎｃｌｉｎｉｃｏｒｔｈｏｐａｅｄｉｃｓｓｃｕｌｐｔｌｎｇ８ｙｓｔｅｍ。ｔ１１ｃｓａｍｐｌＩ“ｇｄａｔａｆｒ。ｍＣＴ

ｓｃａｎ

ｉｍ８９ｅｍｕｓｔｂｅｏｐｔｉｍｉｚｅｄａｎｄｓｍｏｏｔｈｅｄｗｉｔｈｍａｔｈｅｍａｔｉｃａｌａｐｐｒｏｘｉｍａｔｉｎｇｍｅｌ｝１。ｄｓ．

Ｉｎ

ｇｅｎｅｒｉｃ

ｍａｔｈｅｍａｔｉｃａｌａｐｐｒｏｘｉｍａｔｉｏｎｍｅｔｈｏｄｓＣｈｅｂｙｓｈｅｖｍｕｌｔｉｎｏｍｉａｌａｐｐｒｏｘｉｍａｔ沁ｎａｌｇｏｍ｝、ｍｈａｓｂｅｔｌｅｒｅｆｆｅｃｔ

ｏｎ

ｒｅｄｕｃｉｎｇａｐｐｒ。ｘｌｍａｔｉ。ｎ

ｅｒｒ。ｒ．Ｔｈｉｓｐａｐｅｒｂｒｏ“ｇｈｔｆ。ｒｗａｒｄ

ａ

ｐａｒａｌｌｅｌＣｈｅｂｙｓｈｅｖｍｕｌｔｌｎｏｍｌａ】ａｐ

ｐｒｏｘｉｍａｔ】ｏｎａｌｇｏｒｌｔｈｍｂａｓｅｄｏｎ

ａ

ｕｎｉｑｕｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｃｏｎｌｐｌｅｘｃｕｒｖｅ，ａｎｄｉｍｐｌｅｍｃｎｔｅｄ

ｔｈｅ

ｐａｒａＩｌｅｌ

ｐ呻ｇｒａｍ

Ｉｎ

ｔｗｏ

Ｊａｖａｍｅｔｈ。ｄｓ．Ｔｈｅｅｘｐｅ“ｍｅｎｔｒｅｓｕ工ｔｓｓｈｏｗ仆Ｌａｔｔｈｅｐａｒａｌｌｃ【Ｃｈｅｂｙｓｈｅｖｍｕｌｔｉｒｍｍｉａｌａｐ～

ｐｒｏｘｉｍａｔｉｕｎａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｏｎ

ｃｏｍｐｌｅｘ

ｃｕｒｖｅ

ｒｅｐｒｅｓｅｎｔａｔｉｏ“ｇｄｔｈｅｓｉｇｎｍｃａｎｔｓｐｅｅｄｕｐａｎｄｂｅｔｔｅｒｃａｈ

Ｌ【－

ｌａｔｉ“ｇｐｒｅｃｉｓｉｏｎｃｏｍｐａｒｅｄｗｉｔｈｎｏｒｍａｌｓｅｑｕｅｎｔｉａＩＣｈｅｂｙｓｈｅｖｍｕｈ】ｎｏｍｉａｌａｐｐｒｏｘｌｍａｔｉ。ｎａｌｇｏｒｉｔｈｎｌ．

Ｋｅｙ

ｗｏｒｄｓ：ｐａｒａｌｌｅｌｃ。ｍｐｕｔｉｎｇ；ｄａｔａａｐｐｒｏｘｌｍａｔｉｏ“；Ｃｈｅｂｙｓｈｅｖｍｕｌｔｉｎｏｍｉａｌ；ｍｕｌｔｉ—ｔｈｒｅａｄ；ＪａｖａＲＭＩ

骨科临床造型系统中，为病人定做人工髋关节形式存放在磁盘上，以便输入机械设计软件或加工时，首先对病人髋关节部位进行ｃＴ扫描得到图像设备进行设计和加工．但这种方法存在着种种弊端，灰度图，然后通过人工提取或图像处理软件提取骨如人工取点时位置误差、取点次序错误、点的疏密不骼内侧，即髓腔曲线的各点．这些原始数据以文件的

均、图像软件处理存在误差等，如果直接用其来造

收椭日期；２００２一（）３

１６

基金璃目：国家自然科学基金资助项目（６９７７３０１４）

作者简介一邶情妮（１

９７３），女，广西柳州人，副教授（在职博士生），主要研究网络计算和并行计算．电话（Ｔｅｌ．）０２１—６２９３２６３２

Ｅ伽Ｉｌ：ｑｆｌｄｅ“ｇ＠８】ｔｕ．ｅｄｕ

ｃｎ

万方数据

第６期

邓倩妮，等：基于复杂曲线表示的切比雪夫多项式拟合并行算法

９０７

型，曲面的轮廓会非常粗糙，生产的人工关节应力分布不理想．造成人工关节的稳定性下降．因此，要对

原始采样点进行数学逼近，用平顺光滑的曲线来表

示人］．关节的轮廓．在常用的数学逼近方法中切比雪夫多项式拟合法…”误差较小，囡此，本文提出了

一个纂于复杂曲线表示的切比雪夫多项式拟合并行

算法ｊ“，并用Ｊａｖａ语言“ｏ实现了该算法．

１数学逼近方法的比较

常用的数学逼近方法有：最小二乘多项式拟合法和切比雪夫多项式拟合法．

（１）最小二乘多项式拟合法．对一批点（ｚ，，计）

（一ｌ，２，…，ｍ）构成的函数关系表，构造”次代数

多项式：

．１）。（ｚ）一“ｏ＋“Ｉｚ＋…＋ｎ。一

使得

ｓ一∑扛Ｐ（妁一ｙ，］２

达到最小，则称多项式Ｐ（ｘ）为ｙ（ｘ）的最小二乘拟台多项式．在求解Ｐ（ｘ）的过程中，会产生较大的误差，使结果变得不可靠甚至难以求解““．

（２）切比雪夫多项式拟合．切比雪夫多项式：

７１。（』）一ｃｏｓ（ｎ・ａｒｃｃｏｓｚ），

一１≤ｚ≤１

对一批点（ｘ．，ｙ．）（ｉ一１，２，…，ｎ１）构成的函数关系表，构造ｎ次代数多项式：

Ｑ。（｝）＝ｄ。，，，。０）＋Ⅱ，丁，０）＋…＋ｎ。丁。（｝）使得

ｓ一∑击［Ｑ（矗）一Ｍ］２

达到最小，则称多项式Ｑ（ｘ）为ｙ（ｘ）的切比雪夫拟合多项式．随着切比雪夫多项式拟合次数的上升，拟合曲线各部分的误差同时减小，且减小得非常迅

速““．

２平面ＣＴ轮廓曲线的特殊表示方法

平面ｃＴ曲线轮廓是一个形状复杂的封闭曲线．由图】可见，复杂的曲线无法用单值函数ｙ一，（ｚ）来表示．因此，引人参数方程组

丁一ｚ（￡），ｙ—ｙ（￡）

来表示复杂曲线，参数￡的物理意义为从曲线上某一基准点起的曲线长度．对不封闭的曲线，这个点一般可以取为曲线的一个端点；对于封闭曲线则可以任意取某个点．参数ｒ的定义区间为［ｏ，工］（Ｌ为曲线总长），也町以将参数￡标准化到区间［ｏ，１］．

万方数据

ｙ１Ｄ

图１

同一横坐标对应多个纵坐标

Ｆｉｇ．１

ＯｎｅＴ—ｃｏｏｒｄｉｎａｔｅｃｏｒｒｅｓｐｏｎｄｅｄ

ｔｏ

ｓｅｖｅｒａｌ

ｖ

ｃｏｏｒｄｉａｎｔｅｓ

实际拟合时，每个平面ｃＴ曲线原始输入的是１列点户，，户。，…，户，，其中点户－与户。。相同．将户。作为基准点，把从户。开始到Ａ之间的折线长度￡，作为参数￡的近似值（ｊ＝１，２，…，ｍ）．参数计算简例如

图２所示．

图２参数计算简例

Ｆｉｇ．２

ＡｎｅｘａｍｐｌｅｏｆｐａｒａｍｅｔｅｒｃａｌｃｕＩａｔｉｎｇ

因此，要将原始的数据点户－（ｚ。，∥，），Ａ（上：，

ｙ２），…，户。（ｚ。，ｙ。）转换为ｑｌ（￡ｉ，ｚ１），ｑ２（ｆ２，茁２），…，ｇ。（￡，，ｚ。）和ｒｌ（ｆｌ，一１），ｒ２（屯，ｙ２），…，ｒ。（ｆ。，ｙ。）．其

中“一０，

轳∑・庀ｉｉ了耳瓦了ｉ了

Ｊ一０

ｌ一２，３，…，ｍ

３切比雪夫多项式拟合并行算法

３．１切比重夫多项式拟台串行算法

切比雪夫多项式拟台串行算法可分５个步骤：（１）求拟合用的参数．对原始ｃＴ片上的每一个数据点户，（ｚ。，ｙ１），声２（ｚ２，弛），…，声。（ｚ，，％）计算它们到基准点户。的折线长度￡，，其中￡，＝Ｏ，

ｆ，一ｆ，一１＋￣／“．一卫，一１）。＋（ｊ，，一ｙ一】）。

≠一２，３，…，ｍ

（２）自变量映射．如果所给区间■，６］上的列表函数为（ｆ．，ｚ．）（ｉ一１，２，…，ｍ，Ⅲ为原始点数目），则通过线形变换

９０８

上海交通大学学报

第３Ｆ卷

ｆ’一｝２ｆ一（ｄ＋６）ｊ／（Ⅱ一６）

把点列￡，∈［“，６］映射到ｚ‘，∈［一】，１］上，从而得到

一组新的点列（一，ｚ．）（ｉ一１，２，…，ｍ）．

（３）若最终要得到的拟合多项式次数为”，则求切比雪夫”＋１次多项式的ｎ＋１个零点，

”，一。０８瓦而“，７一ｌ，２，…，”＋ｌ

ｗ，一ｃｏｓ害三去“，ｉ—ｌ＇２＇…，”＋ｌ

（４）以新的列表函数（ｆ：，ｚ，）（ｆ一１，２，…朋）为

原始数据进行分段低次插值，再以切比雪夫”＋１次

多项式７１一（ｚ）的零点Ｗ，为自变量代人插值多项

式求出对应的ｚ：．

（５）将（ｗ，，ｚ÷）代人下式：

一、；塾一一詈窑ｒ㈨“

求出ｄ，（ｉ—ｏ，１，…，ｎ），得ｎ次多项式

Ｑ。（ｆ）一日。Ｙ１０（ｆ）＋“ｌ丁ｌ（ｆ）＋…＋ｎ。７１。（ｆ）３．２切比雷夫多项式拟合并行算法

设共有ｍ—ｃ×ｄ个点，其中并行处理机为ｃ

台，ｄ＞ｎ将计算参数“，ｏ矿”，￡。的任务平均分配到

ｒ台处理器．每台处理器并行地以该处理器分配到的第一个输入点（对Ｊ号处理器该点为户Ⅳ）为基准开始计算参数‘，即：

处理器１，输入户ｌ，Ａ，…，∞，计算￡。，ｆ２，…，“；处理器２，输入加，ｐｄ十１，…，户２ｄ，计算如＋ｌ，￡¨２，

：

处理器ｆ，输入Ａ一一，加一“，，…，户。，计算

ｔⅢ一ｄ｝１，｝ｍ

ｄ＋２＇…＇￡。．

对第，（Ｊ＝ｌ，２，…，ｆ）台处理器，令如一ｏ，

ｚ，＝￡，一１＋￣／（ｚ．一七．一１）２＋（弘一”＿１）２

ｉ一∥＋１，…，（Ｊ＋１）ｄ

当处理器１计算出白，立即将之传给处理器２，

处理器２在完成初始计算后，将所有的参数￡，（一ｄ

＋１，ｄ＋２，…，２ｄ＋１）都加上“如果此时处理器２已经计算出ｆⅢ则马上计算｝。一一￡口＋妇，并将￡。一立即传递给处理器３．处理器３在计算参数ｆ时要加上ｆ。一，这时处理器２可以并行地做余下的加法操作．以此类推．而处理器ｆ则需要把￡，广播给所有处理器３，以便下一步计算．

该方法在计算点与点距离时可以完全地并行，最后相加时类似流水操作．计算步为２ｄ十ｃ一１，而不采用并行流水操作，串行计算需要２出步．

在剩余步骤中，数据相关性主要表现在同一组数据前后的相关性，并将它们平均分配给多台处理

万方数据

器．整个并行计算的时空图如图３所示．在求取参数的过程中，各台处理器之间存在通信，以流水线的方式工作；在后面的各步中，处理器之间不存在通信，它们可以并行求出切比雪夫多项式系数的部分值，然后传给一个主控程序求出切比雪夫多项式系数．

５

髂４副３

烈２

１

口计算■通信开销

计算步骤

图３切比雪夫多项式拟合并行计算时空图

Ｆ１９．３

ｒＩ、１ｍｃｇｒａｐｈ。ｆ

ｐａｒａＩ】ｅｌ

Ｃｈｅｂｙｓｈ㈣ｕ【ｔｌｌｌｏｍｌａ

ａｐｐｒｏⅪｍａｔｉ。ｎａｌｇｏｒｌｔｂｍ

４实现并行处理

目前主流的并行编程环境有共享变量和消息传递等模式．共享变量编程模型（如Ｐｔｈｒｅａｄ）假设单地址空间，无需进行数据分配，适于开发细粒度并行性，但它们不存在广泛接受的标准＋对平台依赖性很大；而在消息传递程序（如ＰｖＭ，ＭＰＩ）中，用户必广泛使用并已经成为并行计算中事实上的标准，但在开发细粒度并行性和平台间无缝移植上仍存在问于解决传统方法中存在的问题．本文采用多线程和远程方法调用（ＲＭＩ）两种方法实现了切比雪夫多项式拟合并行计算．

（１）用Ｊａｖａ多线程进行切比雪夫多项式拟合．Ｅｎｔｅｒｐｒｉｓｅ４５０上

度由线程数目（１，２，３，４）表示，服务器配置为：４路对称多处理ＳＵＮ

ＵｌｔｒａＳＰＡＲＣ一Ⅱ（２９６ＭＨｚ）

ＭＢ内存，ｓｏｌａｒｉｓ２．６操作系统，ＪＤＫｌ．２

（ＪＩＴ，ＮａｔｉｖｅＴｈｒｅａｄ）．９０次切比雪夫多项式拟合性

能测试结果如表１所示．

４个ｃＰｕ服务器ｓｕｎ

Ｅｎｔｅ７ｐｒｊｓｅ

４５０的性能测试结果

Ｔａｂ．１

Ｐｅｒｆｏｒｍａｎｃｅ

ｔｅｓ“ｎｇｒｅｓｕｌｔｓ

ｏｎ

Ｓｕｎ

Ｅｎｔｅ。ｐｒｉｓｅ

４Ｓ０

（２）用ＪａｖａＲＭＩ在工作站Ｃｌｕ“ｃｆ上进行切比

须为进程显式地分配数据和工作负载，虽然它已被题．Ｊａｖａ语言所具有的可移植性和平台无关性有利在一台４个ｃＰｕ的服务器ｓｕｎ

用多Ｊａｖａ线程实现切比雪夫多项式拟合并行计算，线程之间通过修改共享变量来传递数据．程序并行ｃＰｕ．５１２

裹ｌ

第６期

邓倩妮，等：基于复杂曲线表示的切比雪夫多项式拟合并行算法

ｇ（）９

雪夫多项式拟合．在４台１二作站上用多Ｊａｖａ线程实现切比雪夫多项式拟合并行计算，线程之间通过ＲＭＩ传递消息．程序并行度由线程数目（１，２，３，４）表示，工作站的配置为：ＳｕＮ

ＵｌｔｒａｓＰＡＲｃ（１４３

采用消息传递模式的实验方案获得更高的加速比，因此，切比雪夫多项式拟合的并行算法是细粒度级的网络密集型计算，适合用共享变量的模式来实现

ＭＨｚ）ｃＰｕ，６４ＭＢ内存，１００Ｂａｓｅ—Ｔ网络接口（与

Ｂａｙｓｔａｃｋ３５０Ｔ交换机相连），ｓ０１ａｒｉｓ

５结语

基于Ｊａｖａ并行编程环境的性能测试表明，提出的切比雪夫多项式拟和并行算法具有较高的加速比．随着Ｊａｖａ语言优化技术的不断提高，纯Ｊａｖａ解决方案和并行数值计算一定可以得到完美的结合．

参考文献：［１］

黄友谦，李岳生．数值逼近［Ｍ］第２版．北京：高等教

育出版社，１９８７．７７

［２］

１３６．

２．５１操作系

统，儿）Ｋ１．１．７（儿Ｔ，ＮａｌｊｖｅＴｈｒｅａｄ）．９０次切比雪

夫多项式拟合性能测试结果如表２所示．

衰２

Ｔａｂ．２

４台ｓｕｎＵｌｔｒａ工作站上选代５次的性能测试结果

Ｐｅｒｆｏｒｍｎｎｃｅ

ｗｏｒｋｓｔａｔｉｏｎｓ

ｔｅｓ“ｎ￡ｒｅｓｕｌｔｓ

ｏⅡｆｏｕｒ

Ｓｕｎ

ＵＩｔｒａ

欧阳联渊计算机数值计算方法［Ｍ］．北京：国防＿：ｌ‘业

出版社．１９９７５５—７６．

［３］孙家昶，张林波，迟学斌，等．网络并行计算与分布式编程环境［Ｍ］．北京：科学出版社，１９９７１０ｊ一１２３

由表１和２可见，这两种方案在处理器台数增加时可以获得较好的加速比．这是由于本文中的切比雪夫多项式拟合并行算法中除了计算参数时各台处理器之间需要同步和通信之外，剩下的步骤各台处理器之间不需要进行通信．由此可见，该并行算法的有效性．另外，采用共享变量多线程的实验方案比

［４］

Ｓｕｎｄｅｒａｍ

ＶＳ，ＧｅｉｓｔＧＡ

Ｈｅｔｅｒｏｇｅｎｅ。ｕｓｐａｒｎ¨ｅ

Ｐａｒ８ＨｅＩ

ａｎｄｄｉｓｔｒｍｕｔｅｄ

ｃｏｍｐｕｔｍｇ［ＪＪｃｏｍｐｕｎｎｇ，

１９９９，２５：１６９９—１７２１．

［ｓ］ＨｏｒｓｔｍａｎｎｃｓＪａｖａ２核心技术卷１：基础知识

２０３．

［Ｍ］．北京：机械工业出版社，１９９９．１５５

上海港国际集装箱运输系统规划

王坚英，

张仁颐

（上海交通大学船舶与海洋工程学院，上海２０００３０）

摘要：综合两种灰色模型得出上海港集装箱吞吐量发展水平的预测值．选取３条主要的国际航线，分别是上海～美国，上海一欧洲、上海一日本．建立单航线单船模型，用黄金分割击进行船型优选．以此为基础．从系统工程的角度结合港、航、船、货４个方面，对上述航线上的船舶进行优化配置，给出船队发展规划，从而为上海国际集装箱枢纽港的建设提供参考．

我国进口液化天然气的海上运输船队

郑海明，

张仁颐

（上海交通大学船舶与海洋工程学院，上海２０００３０）

摘要：探讨了我国进口液化天然气（Ｉ．ＮＧ）海上运输船队的组织，为我国进口ＬＮＧ项目建立了合理的船队规划模

型．一些文献中采用的船队规划模型在胃ｊ单纯形法求解时得出构成船队的船舶数量为非整数而与实际情况不符，

但采取圆整的方法叉会带来较大误差．针对这种情况，在提出的新模型外屡加入对船舶数量进行模失搜索的方法，

使得求解出的船队规划符合实际情况，得出了我国进口ＬＮＧ船队的最优规划，为我国进口ＬＮＧ项目的开展提供了参考

万方数据