Page 20 - 中国仿真学会通讯2020第1期

ＰＡＲＡＬＬＥＬ ＩＮＴＥＲＶＩＳＩＢＩＬＩＴＹ ＡＬＧＯＲＩＴＨＭ
ＯＮ ＧＰＵ

Ｌｉａｎｋａｉ Ｙａｏ１，２， Ｇａｎｇ Ｇｕｏ１．３
１ Ｉｎｎｏｖａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ， Ｂｅｉｊｉｎｇ Ｈｕａｒｕ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ＬＴＤ

２ ｙａｏｌｋ＠ ｉｃｌｏｕｄ．ｃｏｍ
３ ｈｎｄｚｇｇ＠ ａｌｉｙｕｎ．ｃｏｍ

Ｔｈｅ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｏｆ ｌｏｎｇ⁃ｄｉｓｔａｎｃｅ ｌｉｎｅｓ ｏｆ ｓｉｇｈｔ ｍｕｓｔ ｃｏｎｓｉｄｅｒ ｔｈｅ ｉｎｆｌｕｅｎｃｅｓ ｏｆ ｔｈｅ ｅａｒｔｈ
ｃｕｒｖａｔｕｒｅ ａｎｄ ｔｈｅ ｐｒｅｃｉｓｉｏｎ ｏｆ ｔｅｒｒａｉｎ ｄａｔａ． Ｏｔｈｅｒｗｉｓｅ， ｔｈｅｒｅ ａｒｅ ｌａｒｇｅ ｅｒｒｏｒｓ ｔｏ ｔｈｅ
ｃｏｍｐｕｔａｔｉｏｎａｌ ｒｅｓｕｌｔｓ． Ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｅｎ ｄｅｖｅｌｏｐｅｄ ｔｏ ｗｏｒｋ ｏｕｔ ｔｈｅｓｅ ｐｒｏｂｌｅｍｓ ｂｙ
ｄｉｖｉｄｉｎｇ ａ ｌｉｎｅ ｏｆ ｓｉｇｈｔ ｉｎｔｏ ｓｅｖｅｒａｌ ｓｅｇｍｅｎｔｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ＧＣＳ ｔｉｌｅｓ ａｎｄ ｃｏｍｐｕｔｉｎｇ ｔｈｅ
ｉｎｔｅｒｓｅｃｔｉｏｎｓ ｗｉｔｈ ｇｅｏｍｅｔｒｉｃａｌ ｃｕｒｖｅｄ ｓｕｒｆａｃｅｓ ｉｎｓｔｅａｄ ｏｆ ｓａｍｐｌｉｎｇ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｔｈｉｓ
ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ ｉｓ ｉｍｐｌｅｍｅｎｔｅｄ ｏｎ ＧＰＵ ｔｏ ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ．
Ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｓｐｅｅｄｕｐ ｏｆ １０ ｔｉｍｅｓ ｉｓ ａｃｈｉｅｖｅｄ．
Ｋｅｙｗｏｒｄｓ： Ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ； ＧＰＵ ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ； ＣＵＤＡ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．

１． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ６ ｗｈｉｃｈ ｈａｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ
ｗｉｄｅ ａｐｐｌｉｃａｔｉｏｎ ｒａｎｇｅ ａｎｄ ｈｉｇｈ ａｃｃｕｒａｃｙ ｈａｓ
Ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ ｐｌａｙｓ ａｎ ｉｍｐｏｒｔａｎｔ ｂｅｅｎ ｄｅｖｅｌｏｐｅｄ ｂａｓｅｄ ｏｎ Ｇｅｏｇｒａｐｈｉｃ Ｃｏｏｒｄｉｎａｔｅ
ｒｏｌｅ ｆｏｒ ｓｉｍｕｌａｔｉｏｎ， ｍｏｄｅｌｉｎｇ， ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｓｙｓｔｅｍ （ ＧＣＳ ） ． Ｌｏｎｇ⁃ｄｉｓｔａｎｃｅ ＬｏＳ ｗｈｉｃｈ ｓｐａｎｓ
ｓｃｉｅｎｔｉｆｉｃ ｃｏｍｐｕｔａｔｉｏｎ１，２，３ ｔｏ ｄｅｔｅｒｍｉｎｅ ｗｈｅｔｈｅｒ ａ ｓｅｖｅｒａｌ ＧＣＳ ｔｉｌｅｓ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｓｅｖｅｒａｌ ｓｅｇｍｅｎｔｓ
ｌｉｎｅ ｏｆ ｓｉｇｈｔ（ ＬｏＳ） ｉｓ ｉｎｔｅｒｖｉｓｉｂｌｅ ａｎｄ ｗｈｅｒｅ ｉｓ ｔｈｅ ｉｎ ｄｉｆｆｅｒｅｎｔ ＧＣＳ ｔｉｌｅｓ ｔｏ ｅｌｉｍｉｎａｔｅ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ
ｏｃｃｌｕｓｉｏｎ ｐｏｉｎｔ． Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ａｎｄ ｄｉｆｆｉｃｕｌｔｙ ｏｆ ｔｈｅ ｅａｒｔｈ ｃｕｒｖａｔｕｒｅ． Ｉｎ ａｄｄｉｔｉｏｎ， ｔｈｅ ｒｅｓｕｌｔｓ ａｒｅ
ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ ａｒｅ ｅｍｂｏｄｉｅｄ ｉｎ ｇｏｔ ｂｙ ｄｅｔｅｒｍｉｎｉｎｇ ｗｈｅｔｈｅｒ ｔｈｅ ｓｅｇｍｅｎｔｓ ｉｎｔｅｒｓｅｃｔ
ｃａｌｃｕｌａｔｉｎｇ ｒｅｓｕｌｔｓ ａｃｃｕｒａｔｅｌｙ ａｎｄ ｒａｐｉｄｌｙ ｗｉｔｈ ｔｈｅ ｔｅｒｒａｉｎ ｃｕｒｖｅｄ ｓｕｒｆａｃｅｓ ｃｏｎｓｔｒｕｃｔｅｄ ｂｙ
ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｉｎｆｌｕｅｎｃｅｓ ｏｆ ｈｉｇｈ⁃ｐｒｅｃｉｓｉｏｎ ｂｉｌｉｎｅａｒ ｉｎｔｅｒｐｏｌａｔｉｏｎ．
ｔｅｒｒａｉｎ ｄａｔａ ａｎｄ ｔｈｅ ｅａｒｔｈ ｃｕｒｖａｔｕｒｅ．
Ｈｉｇｈ⁃ｐｒｅｃｉｓｉｏｎ ｔｅｒｒａｉｎ ｄａｔａ ｉｓ ｓｔｏｒｅｄ ｉｎ
Ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｉｎｔｅｒｖｉｓｉｂｌｉｔｙ ａｌｇｏｒｉｔｈｍ Ｒｅｇｕｌａｒ Ｓｑｕａｒｅ Ｇｒｉｄ （ ＲＳＧ ） ｍｏｄｅｌ． Ｔｈｅ
ｕｓｉｎｇ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ４，５ ｓｕｃｈ ａｓ Ｊａｎｕｓ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｃｏｍｐｕｔｉｎｇ ｉｎ ｅｖｅｒｙ ＲＳＧ ｉｓ ｍａｓｓｉｖｅ，
ｍｅｔｈｏｄ， Ｄｙｎｔａｃｓ ｍｅｔｈｏｄ， Ｍｏｄｓａｆ ｍｅｔｈｏｄ ａｎｄ ｒｅｐｅｔｉｔｉｖｅ ａｎｄ ｒｅｌａｔｉｖｅｌｙ ｉｎｄｅｐｅｎｄｅｎｔ． Ｆｏｒ ｔｈｉｓ
Ｂｒｅｓｅｎｈａｍ ｍｅｔｈｏｄ ｈａｄ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ｔｈｅ ｋｉｎｄ ｏｆ ｃｏｍｐｕｔｅ⁃ｉｎｔｅｎｓｉｖｅ ａｌｇｏｒｉｔｈｍ， ＣＵＤＡ
ａｃｃｕｒａｃｙ ｏｆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｒｅｓｕｌｔｓ ｉｎｅｖｉｔａｂｌｙ． （ Ｃｏｍｐｕｔｅ Ｕｎｉｆｉｅｄ Ｄｅｖｉｃｅ Ａｒｃｈｉｔｅｃｔｕｒｅ） ｈａｓ ｔｈｅ
Ｆｉｒｓｔｌｙ， ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｅａｒｔｈ ｃｕｒｖａｔｕｒｅ ｗａｓ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ７ ｔｏ ｉｍｐｌｅｍｅｎｔ ｐａｒａｌｌｅｌ
ｎｏｔ ｔａｋｅｎ ｉｎｔｏ ａｃｃｏｕｎｔ ｅｓｐｅｃｉａｌｌｙ ｆｏｒ ｌｏｎｇ⁃ｄｉｓｔａｎｃｅ ｃｏｍｐｕｔｉｎｇ ｏｎ ＮＶＩＤＩＡ Ｇｅｎｅｒａｌ Ｐｕｒｐｏｓｅ ＧＰＵ．
ＬｏＳ． Ｓｅｃｏｎｄｌｙ， ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｐｅｒｆｏｒｍａｎｃｅ
ｗｏｕｌｄ ｄｅｃｒｅａｓｅ ｗｉｔｈ ｉｍｐｒｏｖｉｎｇ ｐｒｅｃｉｓｉｏｎ ｏｆ ｔｅｒｒａｉｎ Ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｉｓ ｐａｐｅｒ ｉｓ ａｓ ｆｏｌｌｏｗｓ．
ｄａｔａ． Ｆｉｎａｌｌｙ， ｏｃｃｌｕｓｉｏｎ ｐｏｉｎｔｓ ｗｅｒｅ ｐｏｓｉｔｉｏｎｅｄ Ｓｅｃｔｉｏｎ ２ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｓｔｅｐｓ ｏｆ
ｊｕｓｔ ｂｙ ｓａｍｐｌｉｎｇ． ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＧＣＳ ｔｉｌｅｓ．
Ｓｅｃｔｉｏｎ ３ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ
Ｔｏ ｍａｋｅ ｕｐ ｔｈｅ ａｂｏｖｅ⁃ｍｅｎｔｉｏｎｅｄ ｓｈｏｒｔａｇｅｓ， ｏｎ ＧＰＵ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｒｅｓｕｌｔｓ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ
ｓｐｅｅｄｕｐｓ ａｒｅ ｇｏｔ ｂｙ ｓｏｍｅ ｎｕｍｅｒｉｃａｌ ｅｘｐｅｒｉｍｅｎｔｓ

１７