CPU/GPU frequency scheduling on smartphones that maintains users' quality of experience (QoE) while reducing power consumption has been studied extensively in the past. Most previous works focused on power-hungry applications such as video streaming or 3D games. However, the majority of people are light to medium users, using applications such as social networking, web browsing, etc. For such interactive applications, it is difficult to reduce power consumption, because their behaviors depend on the user's interactions and are hard to characterize. In this paper, we tackle this challenging problem by considering the influences of user contexts on their interaction behaviors. A context-aware CPU/GPU frequency scheduling governor is proposed that allocates CPU/GPU frequencies just enough to meet the workload under different stages of user interaction. Evaluations show that the proposed governor can save power consumption up to 25% compared to the default governor while keeping the users satisfied with the QoE.

Mobile devices such as smartphones and tablets have become our daily necessities. People spent a lot of time using their smartphones, especially on interactive applications such as social networks, web browsing, and games. To conserve power consumption of such applications becomes ultimately important. Prior works try to save power by balancing performance and workload. These approaches are not comprehensive because they do not take user experience (or Quality of Experience, QoE) into account. Overlooking this factor may turn out to subscribe an excessive performance that the user cannot even perceive, leading to a waste of power. Users' QoE is affected by many factors, including their contexts and the stage of the application. Estimating the QoE requirements for different situations is not only complicated but also crucial. In this paper, we attack this complex problem by first predicting the execution stages of the interactive applications and then applying a stage-based, context-aware, QoE-driven governor (SCQ) to adjust the CPU frequency. Experimental results show that our approach can save 23% more power than the default governor without affecting users' QoE.

User-centric power management in smartphones aims to conserve power without affecting user's perceived quality of experience. Most existing works focus on periodically updated applications such as games and video players and use a fixed frame rate, measured in frame per second (FPS), as the metric to quantify the display quality of service (QoS). The idea is to adjust the CPU/GPU frequency just enough to maintain the frame rate at a user satisfactory level. However, when applied to aperiodically-updated interactive applications, e.g. Facebook or Instagram, that draw the frame buffer at a varying rate in response to user inputs, such a power management strategy becomes too conservative. Based on real user experiments, we observe that users can tolerate a certain percentage of frame drops when running aperiodically updated applications without affecting their perceived display quality. Hence, we introduce a new metric to characterize display quality of service, called the frame drawn ratio (FDR), and propose a new CPU/GPU frequency governor based on the FDR metric. The experiments by real users show that the proposed governor can conserve 17.2% power in average when compared to the default governor, while maintaining the same or even better QoE rating.

The emerging edge computing is poised to move computing and intelligence to the network's edge so as to be close to the data sources for fast responses and reduced network traffic. In edge computing, edge devices need to encompass a wide variety of applications or services, from data preprocessing, intelligence inference, to multimedia human interface. Many such applications are well suited for special-purpose hardware accelerators. With the increasing number of accelerators on the edge devices, a promising architecture for edge devices is an asymmetric heterogeneous multicore that incorporates one or more microcontrollers to offload accelerator scheduling and interrupt handling from the main CPU, as exemplified in the NVIDIA Deep Learning Accelerator (NVDLA). To develop such computing systems, virtual platforms such as QEMU are often used. Unfortunately, QEMU only supports symmetric homogeneous multicore systems. In this paper, we tackle the challenging problem of supporting asymmetric heterogeneous multicore systems on QEMU by considering two possible implementation strategies: one-process and multi-process. The challenges are discussed and our implementations are presented. The two approaches are then compared qualitatively and quantitatively.

Trace-driven simulation has been used widely for architectural exploitation in electronic system-level (ESL) designs for complex SoCs (system-on-chips). Most often the trace files are provided by third parties without source code. This makes it difficult to process and manipulate the trace files, e.g. to identify the region of interest (ROI), for efficient and more focused simulations. It is thus necessary to deduce high-level structures and patterns in the trace to facilitate such manipulations. This can be viewed as a reverse engineering process to derive the dynamic control flow of the original program from its execution trace. Furthermore, after the high-level structure is manipulated, it is also important to generate a new trace from the resultant structure that preserves the characteristics of the original trace for effective trace-driven simulations. The problem becomes even more difficult if the trace was generated from a parallel program because of the complex interactions between the multiple threads of executions. In this paper, a novel scheme to reverse-engineering the program execution trace is proposed, which can obtain the high-level dynamic control structure of the original parallel program as well as regenerate a similar trace from the derived structure, all without referencing the source code. The effectiveness of the proposed scheme is evaluated and verified with extensive experiments.

Marathon is very popular in recent years. However, finishing the game is no easy task, especially for beginners. Regular practices and training are needed. With the availability of wearable devices, it is possible to develop virtual coaches that monitor the progresses of individual runners closeup and guide them through tailor-made training schedules. Unfortunately, most existing wearable devices only record physiological signals of the runners and rely on off-line processing to provide feedbacks. In this paper, we present the design and development of an on-line virtual coach, which performs real-time tracking and analysis of the physiological status of the runner and suggests appropriate adjustments on the exercise intensity. The proposed virtual coach is a pure software solution and can work with any wearable device that monitors the heart rate and running speed of the runner. The main challenge of our system is to predict when the runner will reach the various running states and instruct the runner to adjust the speed just ahead of time so that her/his body can react in time to maintain the required training intensity. Experiments on real users show that our proposed algorithms can correctly predict the running states of the runners and help them to better maintain the required intensity to maximize the training effects.

General-purpose computing on graphics processing units (GPGPU) can provide orders of magnitude more computing power than general purpose processors (CPU) for highly parallel applications. For such parallel applications, the memory traffic pattern of GPGPUs behaves considerably different from that of CPUs. This gives rise to opportunities for optimizing the on-chip interconnection network (NoC) of GPGPUs. In this work, we first investigate the characteristics of GPGPU memory traffic of typical benchmarks and categorize the memory traffic patterns. Different traffic patterns require different throughput in the request and reply paths of the NoC to match the network load. To meet this requirement, we examine the feasibility of scaling the network frequency dynamically to balance the throughput of the request and reply networks. The decision is guided by monitoring some shader cores to identify the memory traffic pattern. Performance evaluation shows that this dynamic frequency tuning design can achieve up to 27% improvement in terms of execution speedup compared to a baseline setting and 7.4% improvement on average.

The popularity of GPS sensors in mobile devices has enabled a new generation of location-based services, in which users record their traveling routes and upload the GPS track points (GTPs) on-the-fly for real-time social sharing, jog journaling, life logging, health care, and map generation. However, directly uploading all GTPs wastes battery energy and network bandwidth on the mobile device, because GTPs are highly redundant. To reduce the redundancies, we propose in this paper the Corner Extraction Technique (CET) to extract the corner points from the GTPs of individual users that can be used to characterize and reconstruct the routes that the user has traveled. Storing corner GTPs requires much less storage space, and transmitting them allows saving in both network bandwidth and energy consumption, leading to optimized GPS-enabled mobile applications. We have conducted both trace-driven simulations and real experiments to demonstrate the merits of the proposed CET approach. The experimental results indicate that: (1) CET results in up to 33 times of compression ratio, (2) CET closely follows the original road segments, and (3) CET saves energy consumption by up to 72%.

3D IC is a promising technology to meet the demands of high throughput, high scalability, and low power consumption for future generation integrated circuits. One way to implement the 3D IC is to interconnect layers of two-dimensional (2D) IC with Through-Silicon Via (TSV), which shortens the signal lengths. Unfortunately, while TSVs are bundled together as a cluster, the crosstalk coupling noise may lead to transmission errors. As a result, the working frequency of TSVs has to be lowered to avoid the errors, leading to narrower bandwidth that TSVs can provide. In this paper, we first derive the crosstalk noise model from the perspective of 3D chip and then propose ShieldUS, a runtime data-to-TSVs remapping strategy. With ShieldUS, the transition patterns of data over TSVs are observed at runtime, and relatively stable bits will be mapped to the TSVs which act as shields to protect the other bits which have more fluctuations. We evaluate the performance of ShieldUS with address lines from real benchmark traces and data lines of different similarities. The results show that ShieldUS is accurate and flexible. We further study dynamic shielding and our design of Interval Equilibration Unit (IEU) can intelligently select suitable parameters for dynamic shielding, which makes dynamic shielding practical and does not need to predefine parameters. This also improves the practicability of ShieldUS.

Switch allocation is a critical pipeline stage in the router of an Network-on-Chip (NoC), in which flits in the input ports of the router are assigned to the output ports for forwarding. This allocation is in essence a matching between the input requests and output port resources. Efficient router designs strive to maximize the matching. Previous research considers the allocation decision at each cycle either independently or depending on prior allocations. In this paper, we demonstrate that the matching decisions made in a router along time actually form a time series, and the Quality-of-Allocation (QoA) can be maximized if the matching decision is made across the time series, from past history to future requests. Based on this observation, a novel router design, TS-Router, is proposed. TS-Router predicts future requests to arrive at a router and tries to maximize the matching across cycles. It can be extended easily from most state-of-the-art routers in a lightweight fashion. Our evaluation of TS-Router uses synthetic traffic as well as real benchmark programs in full-system simulator. The results show that TS-Router can have higher number of matchings and lower latency. In addition, a prototype of TS-Router is implemented in Verilog, so that power consumption and area overhead are also evaluated.

Automatic track and prediction of consumer behaviors involve huge commercial interests and have been studied extensively in the past. We have seen very successful application of such techniques on online consuming behaviors. However, it is still very challenging to predict consumer behaviors in physical stores, because many operations in the middle are not digitized. As smartphones are becoming indispensible in our daily life, we propose to build a framework, called ConsumSense, into the smartphones that observes in close-up the physical consuming behavior of the user and predicts his/her future purchases. Our framework addresses two difficult issues: (1) how to use the limited number of sensors on a smart phone to observe and predict the consuming behavior of its user? (2) how to verify and correlate the purchases? To demonstrate the feasibility of the proposed framework, we have developed the framework on Android and evaluated it by asking 14 participants to conduct a 3-week experiment by using Easy card during their daily life. The results show that time and location are the most important contexts for predicting consuming activities and our framework can achieve a 76% prediction accuracy.

Deploying radio-connected Internet-of-Things in an indoor environment is challenging. Most deployment methods are based on the radio range to determine the density or distance to place the nodes. Unfortunately, the surrounding obstacles such as walls and furniture make the communication pattern unpredictable. It follows that a well-planned IoT deployment plan that guarantees full connectivity on the drawing board may result in disconnected system when deployed on-site. A practical IoT deployment tool must cope with the difference in offline planning and on-site deployment. In this paper, a practical tool is introduced that deploys a network of IoT incrementally for indoor environments. The tool ensures node connectivity in the field despite environmental obstacles. The deployment process is divided into three main phases: offline deployment, online deployment and optimization. Each phase of the tool aims to place as few relay nodes as possible but always ensure full connectivity. The effectiveness of the tool is evaluated through real deployment.

Over the past few years, personal sensing applications, such as travel path sharing and location recording, have been more and more popular. These applications use GPS sensors to record track points on smartphones and upload the track points to clouds in real time for information sharing. However, uploading a lot of GPS points may lead to heavy network traffic and much higher power consumption. To address the problem, we present corner extraction by GPS filtering (CEGF) that extracts corner feature GPS points (CFGPs) from GPS track points (GTPs). Applications only need to upload the CFGPs to save the uploading energy on smartphones. CFGPs can be regarded as characteristic points of corners to represent the corresponding roads. To reduce the number of uploaded points, we use CEGF to filter out the CFGPs from a large amount of GTPs.

Launch delay has been an important factor affecting users' experiences in mobile multimedia applications. To launch applications quickly, modern mobile systems such as Android usually keep inactive applications in the background and manage them through an LRU-based activity stack. Whenever the user wants to run and interact with a background application again, that application can be switched back into the foreground quickly from the activity stack without delay in initializing the applications anew. Since background multimedia applications often continuously consume the battery power of the smart phone, the challenge is to effect a balance between application launch delay and battery lifetime. In this article, we propose innovative application management strategies that terminate “unbeneficial” background applications to save energy and pre-launch “beneficial” applications to improve the application launch delay. The proposed strategies are evaluated through a trace-driven simulation and a real experiment. The results show that the average application launch delay can be reduced by 15% while the average battery lifetime is increased by 18%.

Asynchronous wakeup schemes have been proposed for ad hoc networks to increase the energy efficiency of wireless communication. The basic idea is to allow a node to sleep when it is idle, and wakeup periodically to check if there are pending transmissions. In this paper, we examine the applicability of asynchronous wakeup schemes to the Mobile Ad Hoc NETworks (MANETs). We discover that, although it is desirable to have nodes with lower mobility to sleep more in reaction to the less-changing link states, in practice this is prohibited due to an unwanted tradeoff between the energy saving and in-time link discovery. All nodes in a network must stay awake frequently based on their highest possible moving speed to avoid network partition. To address this problem, we propose a new wakeup scheme, named Unilateral- (Uni-) scheme, for MANETs that allows nodes with slower moving speed to sleep more without losing the network connectivity. The Uni-scheme supports both the entity mobility and group mobility of nodes, thus has broad applicability. Theoretical analysis and simulation are conducted and show that the Uni-scheme can render significant energy saving as compared with the previous arts.

As chip multiprocessors keep increasing the number of cores on the chip, the network-on-chip (NoC) technology is becoming essential for interconnecting the cores. While NoCs result in noticeable performance boost over conventional bus systems, they consume a non-negligible fraction of the system power. One promising solution is to dynamically adjust the working frequencies/voltages of the switches as well as the links between switches in the NoC to match the traffic flows. The question is when to adjust and by how much. Most previous works take a passive approach by reacting to fluctuations in local traffic flows. Unfortunately, this approach may be too slow and too conservative in adjusting the working frequencies/voltages. Since applications often exhibit periodic behaviors, we propose a hardware mechanism to proactively adjust the frequencies/voltages of switches and/or links in NoC by predicting the application runtime traffic. The evaluations show that our design achieves 86% dynamic power savings of the links in the on-chip network, and the resulting overheads from mispredictions are tolerable.

Network-on-chip (NoC) is very important for many applications, such as many-core architectures and application-specific usages. For exploring the design space, several approaches have been proposed with different considerations. In this paper, inspired by bloom filters, we propose Attackboard, a novel design for exploring the design space of NoC, which satisfies accuracy, space efficiency, and simplicity. To justify the usage of Attackboard, a parallel object detection program is used as the benchmark program to evaluate the performance of a specific NoC. By comparing the results with an execution-based simulator, it shows that Attackboard simultaneously achieves the requirements of fast speed, simplicity, and accuracy.

Cloud computing will play an essential role in smart power grid by providing a cost-efficient, scalable IT platform for the delivery and management of electricity. A key component in the cloud-based smart power grid is the intelligent electronic devices (IEDs), which monitor, control, and protect the power system, and collect data back into the cloud for analysis and management. To maintain proper and robust operations of the power system, the collected data must be time-stamped under a common time reference. This in turn demands that the clocks of the distributed IEDs be synchronized to the required precision. A viable approach is to equip some of the IEDs with the Global Positioning System (GPS) as the time references and use the communication links already existing between the IEDs to synchronize the clocks of those without GPS. The question is, given a set of such references nodes, how to decide whether the clocks of all the IEDs can be synchronized to the required precision. If not, how can one add fewest reference nodes to meet the requirements? This paper addresses these issues and proposes efficient algorithms to solve the problems.

Battery energy is one of the most critical resources in a handheld device. Modern designs for handheld devices thus call for optimized use of system power. To develop power-efficient systems, it is essential to understand how power is consumed throughout the system. A promising approach is to measure the power consumption of the system and then match the measurements with the profiled system events. The latter then provides information about how the system consumes power. However, existing tools mostly profile only at the process level due to problems such as profiling overhead and event synchronization. Modern handheld systems, such as Android, complicate the problem further because of the extra layers of software such as Java runtime environment and libraries. To address the above challenges, this paper presents ANEPROF, Android Energy Profiler - a profiling tool for Android that allows energy profiling down to the function level. The design issues and considerations are discussed and its implementation is described. The performance of the tool is evaluated by comparing with other profiling methods.

The most important information in transforming a 2D image into a 3D image is the depth of each pixel in the image. However, a normal 2D image usually does not contain such information, which makes the transformation impossible. On the other hand, for certain types of pictures, such as personal portraits, it is possible to infer crude depth information from their known contexts and properties. Unfortunately, depth map generation is very involving and, if executed on a mobile phone, will consume a lot of energy. This is undesirable, particularly when the mobile device is running out of battery. The application must be aware of the energy status of the system, make appropriate tradeoffs, and then adapt accordingly. This paper presents such an energy-aware, 2D-to-3D image transformation tool for personal portraits on mobile phones. The tool will choose a suitable depth-map generation algorithm based on the remaining energy of the device. We will discuss how to make the tradeoffs and evaluate the idea on real machines.

Asynchronous wakeup schemes have been proposed for ad hoc networks to increase the energy efficiency of wireless communication. The basic idea is to allow a node to sleep when it is idle, and wakeup periodically to check if there are pending transmissions. In this paper we examine the applicability of asynchronous wakeup schemes to the Mobile Ad Hoc Networks (MANETs). We discover that, although it is desirable to have nodes with lower mobility to sleep more in reaction to the less-changing link states, in practice this is prohibited due to an unwanted tradeoff between the energy saving and in-time link discovery. All nodes in a network must stay awake frequently based on their highest possible moving speed in order to avoid network partition. To address this problem, we propose a new wakeup scheme, named Unilateral- (Uni-) scheme, for MANETs that allows nodes with slower moving speed to sleep more without losing the network connectivity. Theoretical analysis shows that the Uni-scheme can render up to 24\% improvement in energy saving as compared with the previous arts.

Integral image becomes a very useful tool in most of the computer vision applications in recent years, and the parallelization strategy is the most popular approach for efficiently generating the integral image. However, most of current parallel integral image generation algorithms are developed based on the dedicated hardware architecture. In this paper, we developed a parallel integral image generation algorithm on Tile64 which is a MIMD-based embedded system. It can be found that our parallel integral image generation algorithm achieved 7.66 times more efficient than the original sequential integral image generation.

The quality of an environmental monitoring application can often be measured by the number of samples collected per unit time. This is to guarantee the reconstruction of the monitored signal. For applications that use wireless sensors for untethered monitoring at rural areas, the challenge is to satisfy the sensing quality while maintaining a long-running operation. Due to the spatial locality of the monitored signal and the oftentimes dense deployment of sensors, the samples taken by a set of nearby sensors can be regarded as equivalent. The problem is how to assign the sampling workload to this set of sensors and maintain a long-running operation. This requires taking account of the energy required to sample as well as to transmit and relay the data to the sink. Previous works on energy-aware routing are not applicable due to the added complexity of sampling assignment. In this paper, we formulate this problem as an optimization problem and present the optimal solution. We compare our algorithm with two commonly used sampling workload assignment algorithms for balancing energy consumption through PowerTOSSIM. The results show that our algorithm can achieve as much as a 25 percent improvement in the residual energy of the critical node, which is the node with the lowest residual energy among all nodes.

Power and thermal distribution are critical issues in chip multiprocessors (CMPs). Most previous studies focus on cores and on-chip memory subsystems and discuss how to reduce their power and control thermal distribution by using dynamic voltage/frequency scaling. However, the on-chip interconnection network, or network-on-chip (NoC), is also an important source of power consumption and heat generation. Particularly, the traffic flowing through the NoC affects directly its power and thermal distribution. Unfortunately, very few works discuss the dynamism of NoC. A key technique for NoC management is to capture its traffic patterns and predict future behaviors. In this paper, we propose a table-driven predictor called Network Traffic Prediction Table (NTPT) for recording and predicting traffic in NoC. The most unique feature of NTPT is its ability to predict end-to-end traffic, rather than switch-to-switch traffic. Thus, more application behaviors can be captured and monitored. Evaluations on Tilera's TILE64 show that NTPT has very high prediction accuracy. Analyses also show that it incurs a low area overhead and is very feasible.

The debris flows caused by typhoon Morakot in August 2009 killed more than 600 people and caused US$ 500 million in damages to agriculture and forestry of Taiwan. Many lives can be saved if we can estimate the occurrence of debris flows and issue timely warnings to inhabitants. Previous literatures [1] have shown that rainfall is highly correlated with debris flows. Thus, the first step to debris flow monitoring and warning is to collect high-resolution, real-time precipitation in the debris-flow-prone areas. In this paper we discuss the considerations of designing a low-cost WSN-based rain gauge grid, which provides highresolution mapping of precipitation. Preliminary experimental results are presented.

In this demo, we present SenPro, a profiling tool that profiles the run-time behaviors of a deployed wireless sensor network (WSN). SenPro runs concurrently with the WSN application and provides information of system execution in a minimally intrusive manner, without requiring any modification to the application being observed. We demonstrate, for a broad class of data gathering applications, how SenPro helps the designer to understand the application behavior by collecting and analyzing the metrics at the centralized sink.

Sensor networks may be deployed to provide external location references to correct configuration errors in indoor robot navigation. Previous work on sensor deployment has considered only sensor and environment models. This paper shows that considering also target models can greatly reduce the deployment cost. We first show how to derive target models for robot navigation and then show that the problem of finding the minimum-cost deployment of a sensor network is NP-hard. The presented algorithms were evaluated through extensive simulations.

With the growing needs for advanced functionalities in modern embedded systems, it is now necessary to integrate multiple processors in the system, preferably on a single chip, to support the required computing complexity. The problem is that such multiprocessor system-on-chip (MPSoC) architecture is very complex and its internal behavior is very difficult to track. An effective tool for profiling the behavior of the MPSoC system is in great need. Such a tool is very usefulduring system designfor exploiting various options and identifying potential bottlenecks. In this paper, we introduce the multiprocessor profiling architecture (MPPA) - a general framework for profiling MPSoC embedded systems. The MPPA framework entails the use of FPGA emulation for the target system, the embedding of performance counters for recording system events, and the development of OS drivers for collecting the profiled data. To demonstrate its use, we show the implementation of an MPSoC emulation system based on Leon3 cores following the MPPA framework. We also show how the MPPA framework and the emulator help the designers to identify performance problems and improve their MPSoC embedded system design.

In a large scale networked virtual environment, users may request various multimedia data in streaming. Although adopting a peer-to-peer (P2P) architecture can make the transmission of on-demand streaming more efficient, most existing research assume that the peers have infinite buffer to cache the entire content and supply the data from there. In this paper, we consider the practical case in which the peers have limited buffer space to cache only a portion of the multimedia content. Due to limited buffer space, peers need effective chunk selection strategies to fetch and discard chunks. We propose a supply-and-demand strategy to estimate the usability of chunks. Peers then select the chunks with a higher usability to fetch and discard the chunks that are useless. Simulation results show that the supply-and-demand strategy selects the chunks accurately and enhances the continuity of playing the stream.

This demo presents a mobile wireless sensor system for debris flow monitoring. The objective of this system is to realize long-term and effective debris flow surveillance using low cost wireless sensors. In the system, a set of robust wireless sensors are designed to deploy on riverbed and cooperatively observe the moving debris flows. Our mobile sensors are intended to be carried along by the debris flow. As the sensors move along, they are able to measure the internal parameters, such as vibration frequency, amplitude, moving direction and velocity, of the debris flow. By utilizing the proposed energy-saving mechanism on the WSN platform, the mobile sensors can continuously operate up to six months with merely two alkaline D cell batteries. The proposed system provides the abilities to collect high-fidelity data for civil engineering applications to analyze and determine the occurrence of debris flows, as well as estimate the damage.

Following the trend of miniature intelligent sensing, wearing small, integrated wireless sensor nodes, such as one with accelerometers and compasses, to capture human body motions may have many applications in medical care and computer animation. In this paper, we demonstrate the use of intelligent sensors to capture human motions for home rehabilitation. We design a game to help a patient to conduct his/her rehabilitation program. For each exercise, the patient is instructed to wear sensors on specified movable body parts. The system will then estimate the quality of the movements and give scores as if it is advised by a therapist. In this way, patients will no longer feel painful and boring as that in traditional rehabilitation, which is typically done in hospitals.

In an event-monitoring wireless sensor network (WSN), the sensors must be waked up fast to engage in active and high-rate sensing when events of interest occur. However, to prolong the lifetime of the network, the sensors should be put into the standby mode as long as possible. There is thus a tradeoff between the standby duration and the wakeup latency. Though the tradeoff is important, what is more important is a flexible transmission schedule that allows the tradeoff to be exploited. In this research, we use debris flow monitoring as a case study to illustrate how the tradeoff between long standby and fast wakeup can be exploited systematically with a flexible transmission schedule.

We present a general framework for building mobility models for floating objects. Such models are useful for studying the behavior of wireless sensors that are deployed to drift along rivers, lakes, oceans, or debris flows. These sensors may be used to track toxic wastes in the water, to study hydrology, or to warn natural hazards. While existing mobility models concentrate on modeling objects moving in autonomy on firm grounds, they cannot be used to describe floating objects that move along with the water flows passively. To build mobility models for such floating objects, our framework entails the use of GPS-equipped wireless sensors that drift along with the water and record the path information. The collected information is converted into a two-dimensional map for modeling the behavior of the floating objects, e.g. generating the simulated drifting paths of the objects. As far as we know, this is the first work on building the mobility models for floating objects.

In this paper, we discuss distributed algorithms to construct ring-like overlays over a subset of scattered nodes in a static, random wireless ad hoc and sensor network (WASN). A ring-like overlay consists of a unidirectional ring plus side paths or loops, in which the given subset of nodes may appear multiple times. Different from a Hamiltonian cycle, a ring-like overlay is easier to construct and more efficient to operate. Yet, it can support many useful control operations in WASN such as mutual exclusion, clock synchronization, and cluster management. Compared with other topologies, a ring-like overlay allows conflict-free two-way communications, supports node ordering, and provides cost-free status feedbacks of operations. In this paper, we first present a distributed algorithm to construct a proximity-aware ring-like overlay in WASN. We then show optimization techniques to adapt the primitive overlays to meet the various application requirements.

Peer-to-peer (P2P) live streaming systems gain a lot of attention recently. Among the various architectures, the gossip-based approach holds great potential and has been used in real systems. In a gossip-based P2P streaming system, peer nodes are grouped together to exchange pieces of the live stream with each other. Maintaining the group and pulling the streaming data from other peers incur nontrivial overhead. This paper proposes CSLive, a P2P streaming system which gathers nodes that have good network proximity into clusters and lets nodes in the same cluster cooperate with each other to pull the stream. Each node in the cluster is responsible for pulling a subset of the stream, while pushing the subset to other nodes in the cluster. With the cooperative operations, a node can receive most streaming data from other nodes in the same cluster, which have good communication quality. The proposed system is evaluated with simulation.

Many data gathering systems require the deployment of heterogeneous sensors to detect various aspects of the target and the use of wireless networks to transmit sensed data to the control center. The data rates of the heterogeneous sensors may range from a few bytes per minute to megabytes per second. To support the transmissions of such diverse rates of data through the wireless network, we propose a novel MAC scheduling scheme, CyclicMAC. CyclicMAC assigns each sensor a cyclic MAC schedule according to the data rates of its sensed as well as relaying data, without causing any channel contention. As far as we know, CyclicMAC is the first to address at the same time all three design issues in MAC scheduling: heterogeneous data rate, end-to-end latency, and storage for scheduling table, for multihop wireless sensor networks.

This work is to augment a debris flow observation and early warning system with wireless sensor networks. Previously, the GIS at Fengchia University has constructed and deployed state-of-the-art, stationary and mobile types of observation systems at nearly 20 sites throughout Taiwan. These sites collect data from sensors ranging from rain gauges and tension cables to ultrasonic sensors and CCD cameras, and transmit them back to the GIS via a lower-orbit satellite uplink in real-time. A new wireless sensor network and middleware system are being designed and implemented to overcome several limitations with the current system. Wireless communication capabilities are being incorporated to enhance the coverage. Previously, most connections between the sensors and the server before the satellite uplink are wired or Wi-Fi with fixed topology and limited range. New wireless interfaces with a 500 m - 1 km range plus energy harvesting devices on the sensors reduces deployment effort and cost. More importantly, it is now becoming possible to construct and deploy brand new types of mobile sensor nodes that move with the debris flow along its path. Such sensor nodes are to be housed in pyramid-shaped, weather-proof capsules that contain motion sensors, GPS and other localization devices, energy harvesting and storage devices, and wireless transceivers. Normally in low-power or standby mode, these capsules would be deployed in the path of potential debris flows. They would stand steadily during normal weather conditions including wind, rain, and water flow. They would get triggered by a threshold motion detector or a rain gauge and start actively monitoring the flow. As it flows with the debris, these capsules transmit their sensor data wirelessly, via other relaying nodes if necessary. Based on the shape and mass of the capsule itself and the velocity, researchers can derive the direction and magnitude of the flow in brand new ways.

Most debris flow monitoring systems deployed today use indirect means to track information regarding debris flows. In this work, we introduce a novel debris flow monitoring system for in-situ and direct tracking of debris flows in real-time. The core idea is to throw wireless sensors into the debris flows and collect flow information as they move along. We will describe the design of the wireless sensors and present some preliminary performance results.

The scale of weather monitoring is limited by the cost of the automatic weather stations (AWS), which is mainly the cost of high precision instruments and long-distance wireless telecommunication equipments. We propose a wireless sensor network (WSN) based AWS, which takes advantage of the low-cost, real-time and infrastructure-free characteristics of WSN [1]. We can therefore extend the scale of weather monitoring without increasing the number of telecommunication equipments. This WSN-based AWS is able to cover a plane and gather multiple sets of weather measurements in real-time at a better data resolution.

Embedded systems are dedicated computers that have fixed functions. Although they have been around for sometime, they have explosive growth recently due to the ability of making smaller and faster semiconductor chips. Embedded systems can be divided into two categories. One has the operating system, the other one is without the operating system. When the functions of embedded systems are getting more and more sophisticated, especially when networking is involved, the operating system is needed to make the embedded system design easier. Although there are several embedded operating systems available, the embedded Linux has gained wide popularity. This paper is about the curriculum design of how to teach an embedded Linux system course. It also gives several references which are helpful for the course..

Broadcast in radio-based wireless networks has been a difficult problem. When a node broadcasts, all nodes within its radio coverage will attempt to relay the message by rebroadcasting, causing excessive radio communication in the region that leads to the broadcast storm problem. Most previous solutions assumed a perfect radio condition with a static, circular coverage. However, in real situations, radio signals are very dynamic and irregular in their coverage. This is especially true for wireless sensor networks, which usually employ low quality radio modules to reduce the cost. Assuming no location information is available, we approach the problem in this paper from two aspects: space and time. To solve the irregularity in space in radio coverage, we propose a scheme that is able to find the neighbors on the rim of the irregular radio coverage region to narrow down the choices of the forwarders. To solve the dynamic in radio coverage, we consider an on-demand, stateless strategy to reduce the overhead of maintaining the state information. Through simulation, we compare the resultant algorithm, called RIM, with Double-Covered Broadcast (DCB) [10], one of the best algorithms proposed so far. The results show that under dense deployment and irregular and dynamic radio coverage, our algorithm performs better.

Most DHT-based P2P search systems assume implicitly that the participating peers contain multiple objects. The distributed hash table (DHT) is used as a directory to store the keys of these objects for efficient lookup. However, maintaining the DHT and keeping its contents fresh require substantial message and storage overhead. In this paper, we study whether it is possible to do without a directory. We consider a special case of the search problem in which each peer is characterized by a single set of attributes and the peers satisfying a given range or k-nearest-neighbor (KNN) query are looked up. The attribute values may change constantly. For this special search problem, we study the feasibility of interconnecting the peers directly using their attribute values instead of using hash keys. The resultant attribute-based overlay network (AON) thus preserves the attribute semantics in the interconnection. Such a distributed structure can easily support range and KNN queries and accommodate dynamically changing attribute values.

Many applications in wireless ad hoc and sensor networks involve only a subset of nodes in the network. A common practice is to form an overlay, such as a mesh or tree, to link the member nodes together. In this paper, we propose two novel distributed approaches for constructing ring-like overlays for static, random ad hoc and sensor networks. A ring-like overlay is a relaxed, unidirectional ring structure, with side paths or loops. Such a structure may be sufficient for global operations such as reliable file multicast, congestion control, and clock synchronization. We evaluate the resultant ring-like overlays by simulation. To the best of our knowledge, this is the first attempt to construct a ring-like overlay on random ad hoc and sensor networks using a distributed approach

Campus navigation and parking assistant system (CaNPAs) is a driver and pedestrian guidance and parking information system designed for use on university, company and government campuses and building complexes. The system communicates with its user via simple portable devices and can provide each user with voice navigation directions along the way to the user's destination. It also can provide information on available parking spaces at and around the user's destination and along the selected route. The system is designed to be low cost, easy to deploy and maintain. This paper describes its architecture and implementation.

Scoped broadcast disseminates a message to all the nodes within a designated physical/logical region in an overlay network. It can be a basic building block for applications such as information search, data broadcasting, and overlay structure diagnostic. In this paper, we study scoped broadcast in peer-to-peer (P2P) overlay networks based on distributed hash tables (DHT). Since P2P networks have very dynamic behavior due to peer joining and departure, it is interesting to know how many peers can be reached with one scoped broadcast. This depends mainly on the cost we would like to pay for maintaining the geometric structure of the DHT-based overlay. The maintenance cost is affected primarily by the failure detection and failure recovery mechanisms. We evaluated the effects of maintenance overhead on scoped broadcast via extensive simulations. The evaluation shows that it is important to exploit fresh nodes as the neighbors of a node. In addition, cooperative failure discovery and recovery can efficiently and effectively disseminate scoped broadcast messages.

One strategy to tackle the complexity and scalability issue in large-scale mobile ad hoc networks (MANETs) is to use extra layers of abstraction. A common tactic is to group the nodes in the network into clusters. The clusters and the paths between them constitute an extra layer of overlay abstraction. To maintain the overlay structure, a head node is often elected in each cluster. The head nodes form a backbone to provide, among other things, passages from one cluster to another. Nonetheless, the use of dedicated head nodes also creates problems such as load and power imbalance. In this paper, we investigate the feasibility of building a cluster-based overlay mesh on MANETs without using cluster heads. Without head nodes, the challenge is in maintaining the overlay structure and performing inter-cluster routing. We will examine one possible scheme through simulation.

The advancement of semiconductor manufacturing technology makes it practical to place a traditional board-level embedded system on a single chip. The evolvement of system-on-chip (SoC) techniques presents new challenges for integrated circuit designs as well as embedded software and systems. To address these challenges, the Ministry of Education (MOE) of Taiwan has been running the VLSI Circuits and Systems Education Program since 1996. This program adopts a top-down approach by forming six domain-specific, intercollegiate consortia. The Embedded Software (ESW) consortium addresses the challenges of embedded software for SoC systems. This paper first introduces the six-consortium architecture and the organization and programs of ESW. We next describe the embedded software curriculum developed by ESW. This curriculum will later be implemented in most universities and colleges in Taiwan to promote the capabilities of embedded software design and implementations. Finally, we present an execution summary of ESW 2004.

Summary form only given. In mobile agent research, agent-to-agent (A2A) communication often relies on an infrastructure of the discovery server to resolve the location of the agents. This not only induces overhead on managing, maintaining and deploying these discovery servers, but also complicates the development of agent applications. While considering scalability and reliability, such an agent discovery infrastructure becomes very sophisticated. We propose a novel A2A communication system, called Armada, which is autonomic and it does not require a discovery infrastructure. Armada is scalable and reliable, and suitable for a wide-area environment with dynamic entities. It does not pose mobile constrains to the agents. Each agent can be globally and uniquely identified without regarding its location. We evaluate Armada through large-scale simulation and prototype measurement in a cluster environment with 35-node desktop PCs. Results from both accesses presents an efficient design of Armada.

Peer-to-Peer (P2P) systems are emerging Internet applications that exploit the resources distributed in the network edges. The resources are aggregated through ad hoc communication among the participating peers, instead of being provided from the centralized servers. The distributed nature of P2P systems avoids performance bottleneck, single points of failure, and censorship of centralized servers. P2P systems also accommodate dynamics in the network and exploit unused resources. P2P systems can generally be classified into unstructured and structured systems. In this paper, we focus on structured P2P systems and review some well-known systems. Their essential features are abstracted, which leads to a tree model to characterize a major family of structured P2P systems.

Peer-to-peer (P2P) overlays are appealing, since they can aggregate resources of end systems without relying on sophisticated infrastructures. Services can thus be rapidly deployed over such overlays. Primitive P2P overlays only support searches with single keywords. For queries with multiple keywords, presently only unstructured P2P systems can support by extensively employing message flooding. We propose a similarity information retrieval system called Meteorograph for structured P2P overlays without relying on message flooding. Meteorograph is fault-resilient, scalable, responsive and self-administrative, which is particularly suitable for an environment with an explosion of information and a large number of dynamic entities. An information item stored in Meteorograph is represented as a vector. A small angle between two vectors means that the corresponding items are characterized by some identical keywords. Meteorograph further stores similar items at nearby locations in the P2P overlay. To retrieve similar items, only nodes in nearby locations are located and consulted. Meteorograph is evaluated with simulation. The results show that Meteorograph can effectively distribute loads to the nodes. Discovering a single item and a set (in size k) of similar items takes O(log N) and (k/c)/spl middot/O(log N) messages and hops respectively, where N is the number of nodes in the overlay and c is the storage capacity of anode.

A wide-area service discovery infrastructure provides a repository in which services over a wide area can register themselves and clients everywhere can inquire about them. We discuss how to build such an infrastructure based on the peer-to-peer model. The proposed system, called Neuron, can be executed on top of a set of federated nodes across the global network and aggregate their resources to provide the discovery service. Neuron is self-organizing, self-tuning, and capable of tolerating failures of nodes and communication links. In addition, it allows the services to be described with arbitrary forms and the system load to be distributed evenly to the nodes. Neuron also supports event notification. We evaluated Neuron via simulation. The preliminary results show that service registration, discovery and service state advertising take at most O(log N) hops to complete.

Proxy prefetch caching aims to reduce the latency in serving web requests by prefetching objects into the proxy cache in anticipation that they might be requested. Thus, when the clients actually request them, these objects can be served directly from the proxy cache without having to be fetched all the way from the remote server. A key component in proxy prefetch caching is the mechanism to determine the profitability of prefetching. A good prefetch advisor must consider not only factors such as the request probability of the prefetched objects, the network bandwidth, and object size, but also the cache space and those objects already in the cache. A unified framework is therefore needed, under which the prefetch advisor can judge whether prefetching some objects by replacing some other objects in the cache can lead to a reduction in the average user access time. In this paper we introduce a framework that unifies prefetch caching and cache replacement with a single index called object profit. The proposed framework is very general that it can be applied to almost any type of web objects, and it considers network bandwidth, cache capacity and replacement, object size, and analysis simplicity together. We will derive the object profit mathematically and then discuss how to apply the framework in practice. The proposed scheme is evaluated with simulation. As the simulation shows, the latency reduction by using the proposed framework can be maximized.

Directory hints help a node in a NOW-based shared memory multiprocessor to keep track of where valid copies of a memory block may reside. With this information the node can fetch the block directly from those nodes on a read miss. In this way the number of network transactions to serve the miss may be reduced and the expensive directory lookup operation may be removed from the critical path. We discuss the issues involved in implementing the directory hint scheme on a NOW-based shared memory multiprocessor and examine one such implementation, which employs a small and fast cache to store the hints. Our simulation results show that the directory hint scheme can effectively reduce the read stall time. Also its performance is very competitive compared with a more expensive implementation which uses a large level-three cache. A drawback of the scheme is that it will introduce extra network traffic. We believe that the state-of-the-art interconnection networks, such as those built upon the SCI Spider (Galles, 1996) and the Intel Cavallino (Carbonaro and Verhoorn, 1996) chips, provide the opportunity to make the directory hint scheme feasible even with the slower network such as the one built by Myrinet switches (N.J.B et al., 1996).

In distributed shared memory (DSM) multiprocessors, a write operation requires multiple messages to invalidate the nodes which share and cache the memory block to be written. The resulting write stall time is a performance hurdle to such systems. One approach to efficient invalidation is to use multicast messages to reach the sharing nodes. We use application driven simulation to evaluate two multicast based invalidation schemes: dual path (X. Lin and L.M. Ni, 1993) and pruning (M.P. Malumbres et al., 1996). Based on our experimental settings, we found that multicast improves invalidation traffic for four of the six evaluated real applications. The remaining two programs are computation intensive, and multicast based validation is less effective. But since they induce bursty communication, we found that multicasts help to relieve the network congestion during those periods of time. Dual path performs a little better than pruning, because it is less sensitive to routing delay in the routers. We also found that cache size is an important design parameter for multicast based invalidation. It is more effective for DSM multiprocessors with large caches.

With the vast advances of Internet services, large-scale and high-performance servers, such as CC-NUMA multiprocessors, are gaining importance in network computing. In a CC-NUMA multiprocessor, the key component to connect a computing node to the interconnection network is the node controller. Node controllers perform protocol processing to transmit messages with other nodes in the system. As the new generation CC-NUMA multiprocessors are moving towards application-specific protocol processing, a node controller will require very powerful protocol processors or engines to provide the flexibility of processing different kinds of protocols. In this paper, we study the design of a thread-based node controller, in which protocol engines have a multithreaded architecture. Multithreading allows protocol processing of different requests to proceed in parallel, whereby reducing blocking and improving response time. Four important design parameters for a multithreaded protocol engine are examined: (1) the number of thread context storages, (2) the number of protocol operation units, (3) the scheduling policy and (4) the thread allocation scheme. From the application-driven simulation on six representative applications, we conclude that the number of thread contexts and protocol operation units have a great impact on the overall system performance. An appropriate thread allocation scheme for invalidation traffic is needed, and prioritizing a thread and scheduling it accordingly are also important for the system performance.

Dynamic branch prediction has been an effective technique for boosting the performance of modern high performance microprocessors. Since hardware predictors only have a limited number of 2-bit counters but programs often have a large, variable number of branches, two branches in the programs may thus be mapped to the same 2-bit counter. Predictions for these two branches may interfere with each other. This, in turn, reduces the prediction accuracy. In this paper, we discuss how a pre-run-time optimization technique, called address adjustment, can help to reduce branch interference. The technique adjusts the addresses of conditional branches in the given program by inserting NOP instructions at appropriate locations. In this way, the mapping between the conditional branches and the 2-bit counters can be controlled and branch interference can be minimized. Address adjustment can be applied at compile or link time, and the latter makes it a walk-time transformation technique. Three possible address adjustment schemes are investigated: constrained address adjustment, relaxed address adjustment, and branch classification. Experimental results show that address adjustment can reduce branch misprediction ratios on existing hardware predictors. Among the three methods, branch classification has the most improvement.

Cache depot is a performance enhancement technique on cache-coherent non-uniform memory access (CC-NUMA) multiprocessors, in which nodes in the system store extra memory blocks on behalf of other nodes. In this way memory requests from a node can be satisfied by nearby depot nodes without going all the way to the home node. This not only reduces memory access latency and network traffic, but also spreads the network load more evenly. We study the design strategy for cache depot that: enhances the network interface of each node to include a depot cache, which stores those extra memory blocks for other nodes; and employs a new multicast routing scheme, which is called the multi-hop worms and works cooperatively with depot caches, to transmit coherence messages. By considering message routing and depot caches together the design concept can be applied even to those CC-NUMA systems that have a non-hierarchical, scalable interconnection network. We have developed an execution-driven simulator to evaluate the effectiveness of the design strategy. Performance results from using four SPLASH-2 benchmarks show that the design strategy improves the performance of the CC-NUMA multiprocessor by 11% to 21%. We have also studied in depth various factors which affect the performance of cache depot.

In this paper, we consider a tree-based routing scheme for supporting barrier synchronization on scalable parallel computers with a 2D mesh network. Based on the characteristics of a standard programming interface, the scheme builds a collective synchronization (CS) tree among the participating nodes using a distributed algorithm. When the routers are set up properly with the CS tree information, barrier synchronization can be accomplished very efficiently by passing simple messages. Performance evaluations show that our proposed method performs better than previous path-based approaches and is less sensitive to variations in group size and startup delay. However, our scheme has the extra overhead of building the CS tree. Thus, it is more suitable for parallel iterative computations in which the same barrier is invoked repetitively.

In this paper we study the effectiveness of sectored caches in reducing false sharing misses on bus-based multiprocessors. In a sectored cache, each cache line is divided into several subblocks. A subblock is a basic coherence unit. When false sharing occurs, the involved cache line needs not be invalidated or transferred, as long as the corresponding subblocks are kept coherent. To facilitate the study, we extend the conventional MESI protocol to sectored caches and define a performance metric called the degree of false sharing reduction to quantify the false sharing reduction on such caches. We simulated the execution of typical benchmarks, FFT, LU, Radix, SORBYR and SORBYC, on sectored caches. Evaluation results show that our scheme can effectively reduce about 30% to 80% false sharing misses and avoid useless coherence operations.

Barrier is an important synchronization operation. On scalable parallel computers, it is often implemented as a collective communication with a reduction operation followed by a distribution operation. In this paper, we introduce a systematic way of generating efficient algorithms to perform barrier synchronization in mesh networks. The scheme works with any base routing algorithm derivable from the turn model. Our scheme extends the turn grouping method with two new algorithms, Tail to Central and Central to Tail, for scheduling the message transmission in the reduction and distribution phase respectively. Simulation results show that our approach can take advantage of the adaptivity of the turn-model based routing algorithms and outperform methods proposed previously.

In this paper, we consider a hardware scheme for supporting barrier synchronization on scalable systems with a 2D mesh network. Our design takes into account of the program execution path in such systems-from programming interfaces down to routers. The hardware router design will be based on the MPI-1 standard. A distributed algorithm is proposed to construct a collective synchronization tree (CS tree) from the nodes participating in the barrier based upon the CS tree, the status registers in the routers are set up and synchronization messages are transmitted along the paths set by the status registers. Performance evaluations show that our proposed method has better performance for barrier synchronization and is less sensitive to variations in group size and startup delay than previous approaches. However our scheme has the extra overhead of building the CS tree. Thus it is more suitable for parallel iterative computations, in which the same barrier is invoked repetitively.

Adaptive nonminimal routing (or misrouting) may move messages away from their destinations to temporarily cope with the dynamic load in an interconnection network. In most cases, misrouting is more powerful and flexible than minimal routing, especially under nonuniform load distribution. However, to take advantage of its misrouting, we have to avoid deadlock, livelock, and starvation in the network and to maintain the network performance across all levels of loading. In this paper, we propose a new flow control scheme for misrouting, called valved routing. Valved routing controls message injection and transmission through logical valves associated with the router ports. Designing routers using valved routing requires a proper choice of design parameters. We will discuss how to find the range of feasible design parameters. Issues in implementing routers using valved routing will also be addressed. We have conducted extensive simulations to compare the performance of routers with and without valved routing. Our simulation results show that valved routing has promising performance advantages, at light as well as heavy network load. Compared with the voluntary misrouting, valved routing performs better in network throughput without sacrificing the latency.>

In this paper, we present methods for scheduling and partitioning behavioral descriptions (e.g., CDFG's) in order to synthesize application-specific multiprocessor systems. Our target application domain is digital signal processing (DSP). In order to meet the user given constraints (such as timing), maximizing the system throughput and minimizing the amount of communication between processors are important. A model of a target processor and the communication device (i.e., bus, FIFO and delay element) is defined as a basis for the synthesis. We use an integer linear programming formulating to solve the partitioning and scheduling problems simultaneously. The optimization complexity for large applications can be reduced by using a simplified formulation. For even larger applications, we propose an iterative partitioning heuristic to solve. Finally, the formulations are extended to take into account of conditional branches, loops, and critical signals.>

The purpose of the Xthreads library is to provide a cheap concurrent programming environment. The design of the Xthreads library is patterned after Xinu, a small and elegant operating system in which all processes share a single address space and hence enjoy reduced overheads in process creation, interprocess communication, and so on. Our approach is to map the Xinu process structure into the Xthreads thread structure in a Unix-like process. Easy extensions and modifications to the Xthreads library are a major objective, accomplished through modularity and layering. We ported Xthreads to the nCUBE2, iPSC860 and RS6000 computers. This paper describes the library, our experiences with its design and implementation, the early performance measurements, and its applicability to simulation modeling.>

A simulation tool, called FM/sup 2/, for analyzing low-dimensional k-ary n-cube networks and their processor/router architecture is presented. The simulator helps to evaluate the network performance in fine-grained, scalable multicomputers by using a predefined simulation language. The language can be used to specify network parameters such as system configuration, flow control mechanism, processor/router interface, channel arbitration, and routing algorithm. Outputs generated by the simulator include average message latency, expected execution time, network hot spots, contention spots, message hit ratio, and size of message pools. A non-blocking send and blocking receive programming model is assumed.>

A study is made of strategies for partitioning nested loop programs on distributed-memory multicomputers. A technique called skewed partition is studied. For certain applications the skewed partition will reduce the amount of synchronization and provide a greater control over the granularity than the commonly used block partition method. To illustrate the idea, two examples, one of image distance transformation and another of solving systems of linear equations, are examined. Results obtained from a 32-node Ncube multicomputer show that the skewed partition improves the performance of these programs more than 50% over the block partition method.>

The authors propose a hybrid static/dynamic scheduling scheme on distributed-memory multiple-processor systems, e.g., distributed systems and multicomputers. Using this self-balancing scheme, computations are first scheduled statically, and then dynamically redistributed to adapt to the run-time environments. The rescheduling operations are directed by a number of program parameters, which can be directly accessed from within the program and will serve as processor load indices. As a result the self-balancing operations can be implemented entirely at the application level, which requires minimal system supports. To illustrate the concept, the self-balancing technique is applied to the asynchronous iterative methods. Various design tradeoffs are discussed, and preliminary performance results on an NCUBE multicomputer are presented.>

The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation and by a simple example (a pipeline image distance transformation algorithm). Pipelined data-parallel algorithms are a class of algorithms which use pipelined operations and data level partitioning to achieve parallelism. Applications which involve data parallelism and recurrence relations are good candidates for this kind of algorithm. The computations are ideal for distributed-memory multicomputers. By controlling the granularity through data partitioning and overlapping the operations through pipelining, it is possible to achieve a balanced computation on multicomputers. An analytic model is presented for modeling pipelined data-parallel computation on multicomputers. The model uses timed Petri nets to describe data pipelining operations. As a case study, the model is applied to a pipelined matrix multiplication algorithm. Predicted results match closely with the measured performance on a 64-node NCUBE hypercube multicomputer.>

For pt.I see ibid., p.470-85. A methodology for designing pipelined data-parallel algorithms on multicomputers is studied. The design procedure starts with a sequential algorithm which can be expressed as a nested loop with constant loop-carried dependencies. The procedure's main focus is on partitioning the loop by grouping related iterations together. Grouping is necessary to balance the communication overhead with the available parallelism and to produce pipelined execution patterns, which result in pipelined data-parallel computations. The grouping should satisfy dependence relationships among the iterations and also allow the granularity to be controlled. Various properties of grouping are studied, and methods for generating communication-efficient grouping are given. Given a grouping and an assignment of the groups to the processors, an analytic model is combined with the grouping results to describe the behavior and to estimate the performance of the resultant parallel program. Expressions characterizing the performance are derived.>

The design of a tool for partitioning and parallelizing nested loops for execution on distributed-memory multicomputers is presented. The core of the tool is a technique called grouping, which identifies appropriate loop partition patterns based on data dependencies across the iterations. The grouping technique combined with analytic results from performance modeling tools will allow certain nested loops to be partitioned systematically and automatically, without users specifying the data partitions. Grouping is based on the concept of pipelined data parallel computation , which promises to achieve a balanced computation and communication on multicomputers. The basic structure of the parallelizing tool is presented. The grouping and performance analysis techniques for pipelined data parallel computations are described. A prototype of the tool is introduced to illustrate the feasibility of the approach.>

A new style of efficient parallel algorithms on distributed-memory multiprocessors is introduced, which exploits parallelism through pipelined parallel computation, or large-grain pipelining. By using macro-pipelining between nodes in the system, large-grain pipelining regulates the flows of data in the multiprocessor so that the degree of overlapping can be maximized and the effect of communication overhead can be minimized. To model pipelined parallel computations, an analytic model is presented, which takes into account both underlying architecture and algorithm behavior. The resultant model is accurate enough to not only predict the performance of a given algorithm, but also assist in algorithm designs for determining optimal design parameters such as the granularity. Results from experiments performed on a 64-node NCUBE multiprocessor match closely to the predicted performance. A systematic procedure for designing pipelined data parallel algorithms from nested loop programs is described. The impact of the second generation distributed-memory multiprocessors on the pipelined parallel computations is also discussed.

A hardware pattern matcher is presented, which searches for patterns on a data flow, such as characters read from a disk. The backing up on the data flow, for a general pattern matching, is avoided by means of a set of cells running in parallel. Each cell can search for a pattern independently, but requires only one one-character comparator. The interesting feature of this search hardware is the use of simple priority line which can dynamically allocate these cells. Further, the number of cells required can be arbitrarily reduced by means of a marking technique which is also accomplished by the priority line. Finally, an information retrieval system, based on this basic pattern matching hardware is presented. Here the content as well as the context search are done by usign the same marking technique.