School of Science and Technology 科技學院
Computing Programmes 電腦學系
| Programme | Bachelor of Science with Honours in Internet Technology |
| Supervisor | Dr. Li Tak Sing |
| Areas | Distributed Systems |
| Year of Completion | 2009 |
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.
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:
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:
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:
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:
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.
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:
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
| No. of points: | 100 | 500 | 800 | 1000 |
|---|---|---|---|---|
| No. of PC(s) | Total execution time (s) **: | |||
| 1* | 0.204 | 2.531 | 6.266 | 8.985 |
| 2 | 0.25 | 2.484 | 6.235 | 8.531 |
| 3 | 0.187 | 2.187 | 5.187 | 7.093 |
| 4 | 0.313 | 1.906 | 4.313 | 6.015 |
| 5 | 0.265 | 1.907 | 4.407 | 6.609 |
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.
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 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.
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 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 Code | Title | Credits | |
|---|---|---|---|
| COMP S321F | Advanced Database and Data Warehousing | 5 | |
| COMP S333F | Advanced Programming and AI Algorithms | 5 | |
| COMP S351F | Software Project Management | 5 | |
| COMP S362F | Concurrent and Network Programming | 5 | |
| COMP S363F | Distributed Systems and Parallel Computing | 5 | |
| COMP S382F | Data Mining and Analytics | 5 | |
| COMP S390F | Creative Programming for Games | 5 | |
| COMP S492F | Machine Learning | 5 | |
| ELEC S305F | Computer Networking | 5 | |
| ELEC S348F | IOT Security | 5 | |
| ELEC S371F | Digital Forensics | 5 | |
| ELEC S431F | Blockchain Technologies | 5 | |
| ELEC S425F | Computer and Network Security | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| ELEC S201F | Basic Electronics | 5 | |
| IT S290F | Human Computer Interaction & User Experience Design | 5 | |
| STAT S251F | Statistical Data Analysis | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| COMPS333F | Advanced Programming and AI Algorithms | 5 | |
| COMPS362F | Concurrent and Network Programming | 5 | |
| COMPS363F | Distributed Systems and Parallel Computing | 5 | |
| COMPS380F | Web Applications: Design and Development | 5 | |
| COMPS381F | Server-side Technologies and Cloud Computing | 5 | |
| COMPS382F | Data Mining and Analytics | 5 | |
| COMPS390F | Creative Programming for Games | 5 | |
| COMPS413F | Application Design and Development for Mobile Devices | 5 | |
| COMPS492F | Machine Learning | 5 | |
| ELECS305F | Computer Networking | 5 | |
| ELECS363F | Advanced Computer Design | 5 | |
| ELECS425F | Computer and Network Security | 5 |
