Indoor localization
Haibo Zhang, David Eyers, George Phillips, Zhiyi Huang
Indoor localization using wireless sensor networks is a fun project which uses wireless sensor networks, accelerometers to track a moving target and display the location inside a building with 3-D animations.
Challenges in the project is the accuracy of the estimated location, given that the radio signals are noisy and reflective inside a building. Automatic sensor calibration and sensor fusion techniques like particle filters will be used to improve the accuracy of the localization.
Train localization with wireless sensor networks
Jothi Nathella Vijayakumar, Adeel Javed, Haibo Zhang, Zhiyi Huang.
Train localization is becoming a necessity for modern train systems. With the information of train locations, passengers can know where their trains are and how long they have to wait to arrive or depart. The information of train locations is even more critical to the scheduling of trains due to safety reasons. Though GPS can provide location data for trains, there are many places such as tunnels where GPS signals are not available. In this project, we are using wireless sensor networks to provide location information for trains. The challenge of the project is that the noises and fast train speeds can affect the accuracy of the location information acquired from the wireless sensor networks.
View-Oriented Transactional Memory
Kai-Cheung Leung, Yawen Chen, Zhiyi Huang.
Traditionally locking is used for concurrency control when multiple processes/threads have to access a shared data object in an exclusive way. This lock-based concurrency control is generally regardednas pessimistic approach where conflicts are resolved before they are allowed to happen. Even though locking is an effective mechanism to resolve conflicts, it could result in the deadlock problem if multiple objects are locked in different orders by multiple processes. Moreover, apart from the deadlock problem, fine-grained locks are tedious for programming, while coarse-grained locks often suffer from poor performance due to lack of concurrency. To avoid the deadlock problem as well as to increase concurrency, Transactional Memory (TM) was proposed. In TM, atomic access to shared objects is achieved through transactions. All processes can freely enter a transaction, access the shared objects, and commit the accesses at the end of the transaction. If there are access conflicts among processes, one or more transactions will be aborted and rolled back. TM will undo the effects of the rolled-back transactions and restart them from the beginning. This transaction based concurrency control is labeled as an optimistic approach where it is assumed nothing will go wrong and if it does go wrong deal with it later.
In terms of performance, both lock-based and TM-based approaches have their own merits in different situations. When access conflicts are rare, the TM-based approach has little roll-back overhead and encourages high concurrency since multiple processes can access different parts of the shared data simultaneously. In this situation, however, the lock-based approach has little concurrency due to the sequential access to the shared data, which results in low performance. To increase concurrency and performance, the programmer has to break the shared data into finer parts and use a different lock for each part. This solution using fine-grained locks often complicates the already-complex parallel programs and could incur deadlocks. On the other hand, when access conflicts are frequent, the TM-based approach could have staggering roll-back overheads and is not scalable due to a large number of aborts of transactions. In such a situation, it is more effective to use the pessimistic lock-based approach to avoid the excessive operational overheads of transactions.
In this project, we propose the novel View-Oriented Transactional Memory (VOTM) paradigm that seamlessly integrates the locking mechanism and transactional memory into the same programming model. VOTM is designed based on the generic principle of our previous View-Oriented Parallel Programming (VOPP) model. In VOTM, shared data objects are partitioned by the programmer according to the memory access pattern of a program. The grain (size) and content of a view are decided by the programmer as part of the programming task, which is as easy as declaring a shared data structure or allocating a block of memory space. Each view can be dynamically created, merged, and destroyed. The most important property for VOTM is that the concurrent access to each view can be controlled separately and can be adjusted in terms of the number of concurrent threads accessing a view. In this way, performance of TM can be greatly improved.
Papers published on this project include:
View-Oriented Transactional Memory, Leung K.C. and Huang Z., The Fourth International Workshop on Parallel Programming Models and Systems Software for High-end Computing, in Workshop Proceedings of the 40th International Conference on Parallel Processing (ICPPW 2011), pp.335-344, 2011, doi:10.1109/ICPPW.2011.10.
Energy saving in parallel and distributed systems
Jason Mair, Yawen Chen, David Eyers, Haibo Zhang, Zhiyi Huang.
Energy consumption is becoming a concern in large scale systems such as servers and clusters for grid and cloud computing due to their popular deployments. This is becoming more prevalent because new issues are arising due to their ever increasing scale, like the increasing demand on the energy grid, and general operational costs including cooling. The total cost of operation is growing so much that in some cases it is likely to start exceeding the initial capital costs for building such a cloud computing center, preventing some business from setting up such facilities. In addition, consumers are concerned about environmental impact of energy consumption. In USA, 70% of electricity is generated from burning fossil fuels, and this is a big contributor of greenhouse gases and global warming. As a result, many companies try to decrease their environmental footprint by focusing on energy efficiency of big energy consumers, including grid and cloud computing data centers. This is achieved through research in green computing, which aims at improving power and energy efficiency in computing facilities. In our research, to avoid ambiguity, we use power and energy in strict terms, i.e. energy = power Viewsinto time.
Previous research in green computing had been focusing on power efficiency of high performance computing. The common metric used is Performance per Watt (PPW), which is often applied to computer hardware and systems, assuming they are always busily running applications. However, power efficiency is not equivalent to energy efficiency, since power efficient systems may still consume a substantial amount of energy when they are idle. Moreover, many real world systems have very low levels of utilization. For example, many data centers only have the utilization of 10% to 50% and could be less than 5% for some computer nodes. Computers do not have good energy efficiency if they consume a lot of power at idle time, even though they may have good power efficiency during execution. This is due to energy been power multiplied by time. Therefore, eventually we should be aiming at energy saving, rather than power saving. Furthermore, even on those busy computer nodes, running applications may have a relatively relaxed targeted performance. That is, they are not concerned about achieving the maximum performance that is possible on the computer system. For example, some computing centers may have a number of applications that need to run once a day, but for each of the applications there is no strict performance requirement, as long as it can be finished in a day. In these situations, new measures and policies could be introduced to save energy, as long as they do not come at the cost of the required performance target.
In this project, we set out to explore new metrics and policies that could be used in multicore nodes of grid and cloud environments, in order to reduce energy consumption without impacting on the performance target of the applications. A unique aspect of this work is combining Dynamic Voltage Frequency Scaling (DVFS) and program parallelism to achieve energy saving on modern multicore computers. Our research uses the multicore computers because they are rapidly becoming the default in consumer electronics, as well as often having theEnergy Efficient Grids, Clouds and Clusters Workshop, In Proceedings of the Eleventh ACM/IEEE International Conference on Grid Computing (GRID 2010), pp.266-273, IEEE Computer Society (2010), Brussels.
Task scheduling in multicore architectures
Quan Chen, Yawen Chen, Zhiyi Huang, Minyi Guo (from Shanghai Jiao Tong University).
Multi-core processors have become mainstream as chip manufacturers like AMD and Intel keep producing new CPU chips with more cores. Modern multi-core computers often use a Multi-Socket Multi-Core (MSMC) architecture in order to obtain more computing power. In the MSMC architecture, multiple multi-core chips share the main memory (RAM), while the cores in the same CPU chip share the L2 or L3 caches. This architecture is popular now and will continue to be a dominating architecture for high performance computing in future. Despite the rapid development of the multi-core technology, a lot of software are yet to be parallelized to utilize the power of multi-core computers. This need has promoted the development of parallel programming environments. Many such environments such as MIT Cilk, Intel Cilk++, Intel TBB, OpenMP have been developed for ease of parallel programming. However, they suffer performance problems with their existing task scheduling policies.
In this project, we are investigating the task scheduling policies and algorithms that can improve the performance of parallel programming environments on MSMC architecture. Papers published on this project include:
CAB: Cache Aware Bi-tier Task-stealing in Multi-socket Multi-core Architecture, Chen Q., Huang Z., Guo M., and Zhou J., in Proceedings of the 40th International Conference on Parallel Processing (ICPP 2011), pp.722-732, 2011, doi:10.1109/ICPP.2011.32.
CLOSE - CLuster Operating System & Environment
Within a cluster environment, we have researched ways to improve the communications between the operating system kernels on the cluster machines. We have developed a light-weight kernel-to-kernel message passing system that give better performance than TCP or UDP and supports broadcast. Cluster monitoring was built on this message passing system. Current projects include cluster-based RAM disk that swaps data over the network to spare memory on other machines.
Power Conservation in Network Devices
This project aims to find ways to save power consumed by fixed and wired network devices such as routers, switches, and desktop computers. The power consumed by the Internet is considerable and is growing. Many devices today are not power friendly. The same applies to some of the protocols and applications.
Embedded Systems
One project is the integration of GPS and inertia measurement to track moving objects like mountain bicycles. The purpose is to record the exact position of the bicycle so its movement can be reconstructed. The data could then be visualised and used for training purposes.
Another project involving model airplanes is exploring ways in which inexpensive hobby type model airplanes can be used in search and rescue operations and infrastructure surveys after a catastrophe such as an earthquake or flood. Current work involves vision based automated landing.