School of Science and Technology 科技學院
Computing Programmes 電腦學系

Applying Distributed Computing using Aglets on Delaunay Triangulation

DUNG Chun Yee

ProgrammeBachelor of Science with Honours in Internet Technology
SupervisorDr. Li Tak Sing
AreasDistributed Systems
Year of Completion2009

Objectives

There are currently billions of computers in the world but most of them are in an idle state. This wastes a large amount of computation resources that could be exploited for solving complicated computational problems. Java mobile agent (Aglets) is a distributed computing technology that allows the distribution of a process to any number of computers in the Internet.

This project demonstrates this concept through the implementation of a very complicated computation problem. The Incremental Insertion algorithm of Delaunay Triangulation is chosen to be the very complicated computational problem. First, a computational and visualized program for Delaunay Triangulation in a single computer is designed and implemented. Next another program for Delaunay Triangulation in a distribution system is designed. The algorithm is then analyzed into a parallelized version. Distributed computing program is implemented based on a Master-Slave design pattern with Aglet. The result from the program in a single computer and the result from the distributed computing program were compared in terms of execution time. Obviously the execution time from the distributed computing program was much shorter. The time reduction showed the benefit of using distributed computing with Aglet.

This paper includes the background of distributed computing, Aglet and Delaunay triangulation, an outline of the algorithm parallelization and Aglet distribution computing system, an evaluation of the benefit of using distributed computing with Aglet, and finally a discussion of the limitations of the improvement.

Background and Methodology

Many mobile agents systems have been developed in the last few years such as Aglets, Telescript, AgentTcl, and MOA. Most agent servers and mobile agents are written in Java for its technical advantages: machine independence and strong typing for security. Java is an interpreted computer language and can therefore execute on a variety of heterogeneous computer platforms. Java mobile agent, Aglets, is focused in this project. Aglet is a popular java based mobile agent platform and library for building mobile agents based applications. The following figures show the different between applet and aglet:

Mobile agents must exist within an execution environment; Tahiti is the Aglets’ execution platform which is shown below:

Delaunay triangulation is one of the fundamental topics in the computational geometry and it is used in many areas, such as terrain modeling (GIS), scientific data visualization and interpolation, robotics, pattern recognition, meshing for finite element methods (FEM), natural sciences, computer graphics and multimedia, etc. Expensive computation is needed for construction. The popularity of Delaunay triangulation is that the algorithm produces the most equiangular triangles of all possible methods. An example is shown below:

 

It has algorithms for parallel computing such as incremental insertion and Divide-and-Conquer. Incremental insertion is chosen. The incremental algorithm consists of two main parts:

  • Locate a triangle (or an edge), containing the inserted point.
  • Insert the point into the current triangulation, making the necessary adjustments.

The following shows an example of inserting a point which splits a triangle and forms 3 or 4 new triangles:

The main methodologies of this project are stated below:

  • Computational and visualized program
  • Analyze incremental insertion task in parallel
  • Distributed computing program with Aglets

For the computational and visualized program, a visualized program is required for testing. The function of this program is to create a simple polygon (clockwise) and generate the random points inside the polygon. Then the Delaunay Triangulation (DT) is shown on the polygon with the random points to display the result. The following shows the main program interface of the computational and visualized DT program:

 

Data parallelism is chosen to be the parallelization method of this project. The data is divided into several parts and perform with the parallel task. Division process and integration process are the two important processes in the parallelization.

 

The division method of division is as follows:

  • Find an approximate center point of the polygon through creating a rectangle which can bounds all the points for estimation that point.
  • Add splitting lines. The separation based on the angle. If the polygon is distributed into 3 parts, the angle of each part is 360/3 = 120.
  • Create a number of distribute data set and record reserved points which are the intersection point between the polygon edge and the splitting line. Each set of data includes the temporary edge and the points which in the bounded area.
  • The data sets are performed DT in parallel using the method described earlier.

The details of the division process is illustrated below:

Integration process is designed one-pass. This means the results of distribution were all collected from the slaves before the integration process. The method of integration is as follows:

  • Perform swapping with all the affected triangles which are on the common edges one by one recursively.
  • Remove (a) the reserved point on the edge and (b) the center point. The details is shown below:

The Master-Slave design pattern is employed in this project. The system is classified into two parts including master aglet and slave aglet. This design pattern defines a scheme whereby a master aglet can delegate a task to slave aglet and is used in the following cases.

  • When an aglet needs to perform a task in parallel with other tasks.
  • When a stationary aglet wants to perform a task at a remote destination.

Above cases make matches to properties of this project. Incremental Insertion of DT can be performed in parallel. Therefore, this design pattern is suitable for this project. The collaboration between the participants in Master-Slave pattern is as following:

  • A master aglet divides the data into several parts.
  • The master creates several slave aglets with subdivision data
  • The slave initialize DT task.
  • The slave moves to remote host and performs their DT task.
  • The slave sends the result to master through message.
  • The slave disposes of itself.
  • The master integrates the results after receive all.
  • The master disposes of itself

Following is the collaboration diagram between the mobile agents:

The action details of the mobile agents between the aglets server and the remote hosts is shown in the following:

Step 1

Step 2

Step 3

Evaluation

The experiment focuses on the comparison of the execution time from two different programs, computing on single computer and computing in parallel with aglet. Four sets of data and five computers of same performance are prepared for the experiment. The sets of data include the same shape simple polygon and the number of random points, which are 100, 500, 800 and 1000 respectively. The points are in uniform distribution. The performance of each computer is “Intel® Core™2 Duo CPU E8200 @ 2.66Hz 2.66Hz, 1.96GB RAM” and is installed the Aglet server. Following is the results of the experiment:
No. of points:1005008001000
No. of PC(s)Total execution time (s) **:
1*0.2042.5316.2668.985
20.252.4846.2358.531
30.1872.1875.1877.093
40.3131.9064.3136.015
50.2651.9074.4076.609
* Computing without parallelize ** Total Execution time includes time for network traffic, division process and integration process.

From the results, we can observe that the execution time of the computing in parallel is shorter. The more points are distributed to remote computers, the more significant reduction in time is resulted. This fulfils part of the expectation of this experiment. However the reduction of executive time does not vary significantly in direct proportion.

In this project, the results of distribution were all collected from the slaves before the data integration. From the time distribution chart as shown below, we can observe that the time of integration is longest process. We can assume that the integration improvement is important.

The control distribution of points does not include in the program. The division process is just based on the degree of angle and the number of division must be based on the factor of 360. The points cannot be not evenly distributed. Following is the execution time of the distributed subdivisions in the experiment:

No. of PC(s)No. of points (each divided part)*:Execution Time (ms) (each divided part)**:Average of Execution Time
2[485, 517][3.25, 4.032]3.641
3[279, 301, 421][1.171, 1.407, 2.562]1.713
4[213, 249, 279, 271][0.687, 0.938, 1.157, 1.14]0.981
5[186, 179, 279, 164, 207][0.5, 0.563, 1.297, 0.656, 1.0]0.803

* Divided point may be more than total point because the points on the splitting line

** Underline means the longest time of execution

From the result, we can observe that the execution time of the computing in parallel is shorter. The more points are distributed to remote computers, the more significant reduction in time is resulted. This fulfils part of the expectation of this experiment. However the reduction of executive time does not vary significantly in direct proportion.

Conclusion and Future Development

On the whole, the objective of this project is accomplished through the experiment of distributed computing with Aglet using DT From the result of the experiment, we can observe that the execution time of the computing in parallel is shorter. However, the result is not significant enough. The original expectation is the execution time varied in direct proportion to the number of distribution. Although our program can be improved as the discussion in Section 3, the radical problem of this project is the selection of the algorithm, Incremental Insertion. The fundamental of this algorithm is calculated in serial. In this project, the task was just parallelized. The parallel efficient was low. Time did not permit to study and implement other advanced kinds of algorithm.

The recommendation for future work on the same topic, another parallel Delaunay Triangulation such as Divide-and-Conquer can be chosen for application. For advancement, the program can be built into 3D version with the related parallel algorithms. Reviewing the whole project, the most difficult part is to study and implement the Delaunay Triangulation which involves complicated calculation. In contrast, the topic of mobile agent is more relatively easy to handle. Many features of the Aglets still have not been exploited in the project. The recommendation for future work is to apply the distributed computing with aglets on areas which are much closer to life matters or public interests, for example, audio/video compression and time scheduling.

Copyright Dung Chun Yee and Li Tak Sing 2009

Jonathan Chiu
Marketing Director
3DP Technology Limited

Jonathan handles all external affairs include business development, patents write up and public relations. He is frequently interviewed by media and is considered a pioneer in 3D printing products.

Krutz Cheuk
Biomedical Engineer
Hong Kong Sanatorium & Hospital

After graduating from OUHK, Krutz obtained an M.Sc. in Engineering Management from CityU. He is now completing his second master degree, M.Sc. in Biomedical Engineering, at CUHK. Krutz has a wide range of working experience. He has been with Siemens, VTech, and PCCW.

Hugo Leung
Software and Hardware Engineer
Innovation Team Company Limited

Hugo Leung Wai-yin, who graduated from his four-year programme in 2015, won the Best Paper Award for his ‘intelligent pill-dispenser’ design at the Institute of Electrical and Electronics Engineering’s International Conference on Consumer Electronics – China 2015.

The pill-dispenser alerts patients via sound and LED flashes to pre-set dosage and time intervals. Unlike units currently on the market, Hugo’s design connects to any mobile phone globally. In explaining how it works, he said: ‘There are three layers in the portable pillbox. The lowest level is a controller with various devices which can be connected to mobile phones in remote locations. Patients are alerted by a sound alarm and flashes. Should they fail to follow their prescribed regime, data can be sent via SMS to relatives and friends for follow up.’ The pill-dispenser has four medicine slots, plus a back-up with a LED alert, topped by a 500ml water bottle. It took Hugo three months of research and coding to complete his design, but he feels it was worth all his time and effort.

Hugo’s public examination results were disappointing and he was at a loss about his future before enrolling at the OUHK, which he now realizes was a major turning point in his life. He is grateful for the OUHK’s learning environment, its industry links and the positive guidance and encouragement from his teachers. The University is now exploring the commercial potential of his design with a pharmaceutical company. He hopes that this will benefit the elderly and chronically ill, as well as the society at large.

Soon after completing his studies, Hugo joined an automation technology company as an assistant engineer. He is responsible for the design and development of automation devices. The target is to minimize human labor and increase the quality of products. He is developing products which are used in various sections, including healthcare, manufacturing and consumer electronics.

Course CodeTitleCredits
 COMP S321FAdvanced Database and Data Warehousing5
 COMP S333FAdvanced Programming and AI Algorithms5
 COMP S351FSoftware Project Management5
 COMP S362FConcurrent and Network Programming5
 COMP S363FDistributed Systems and Parallel Computing5
 COMP S382FData Mining and Analytics5
 COMP S390FCreative Programming for Games5
 COMP S492FMachine Learning5
 ELEC S305FComputer Networking5
 ELEC S348FIOT Security5
 ELEC S371FDigital Forensics5
 ELEC S431FBlockchain Technologies5
 ELEC S425FComputer and Network Security5
 Course CodeTitleCredits
 ELEC S201FBasic Electronics5
 IT S290FHuman Computer Interaction & User Experience Design5
 STAT S251FStatistical Data Analysis5
 Course CodeTitleCredits
 COMPS333FAdvanced Programming and AI Algorithms5
 COMPS362FConcurrent and Network Programming5
 COMPS363FDistributed Systems and Parallel Computing5
 COMPS380FWeb Applications: Design and Development5
 COMPS381FServer-side Technologies and Cloud Computing5
 COMPS382FData Mining and Analytics5
 COMPS390FCreative Programming for Games5
 COMPS413FApplication Design and Development for Mobile Devices5
 COMPS492FMachine Learning5
 ELECS305FComputer Networking5
 ELECS363FAdvanced Computer Design5
 ELECS425FComputer and Network Security5