We propose new real-time architectures for monitoring underwater oil and gas pipelines by using Underwater Wireless Sensor Network (UWSN). These monitoring architectures combine a real-time UWSN with nondestructive In Line Inspection (ILI) technology. A communication between UWSN and ILI tools adds a meaningful feature that allows the UWSN deliver crucial information regarding pipeline failures within minutes. Currently, there is no established communication system between UWSN and ILI. These suggested architectures will help reduce the pipeline defect detection time, dealing with corrosion, cracks, welds, and pipeline wall thickness through the improvement of data transfer from the pipeline to the processor. Moreover, the extraction of useful information and its timely delivery to the onshore main station will lead to decrease of issue occurrence.

BACKGROUND: Automatic segmentation and localization of lesions in mammogram (MG) images are challenging even with employing advanced methods such as deep learning (DL) methods. We developed a new model based on the architecture of the semantic segmentation U-Net model to precisely segment mass lesions in MG images. The proposed end-to-end convolutional neural network (CNN) based model extracts contextual information by combining low-level and high-level features. We trained the proposed model using huge publicly available databases, (CBIS-DDSM, BCDR-01, and INbreast), and a private database from the University of Connecticut Health Center (UCHC). RESULTS: We compared the performance of the proposed model with those of the state-of-the-art DL models including the fully convolutional network (FCN), SegNet, Dilated-Net, original U-Net, and Faster R-CNN models and the conventional region growing (RG) method. The proposed Vanilla U-Net model outperforms the Faster R-CNN model significantly in terms of the runtime and the Intersection over Union metric (IOU). Training with digitized film-based and fully digitized MG images, the proposed Vanilla U-Net model achieves a mean test accuracy of 92.6%. The proposed model achieves a mean Dice coefficient index (DI) of 0.951 and a mean IOU of 0.909 that show how close the output segments are to the corresponding lesions in the ground truth maps. Data augmentation has been very effective in our experiments resulting in an increase in the mean DI and the mean IOU from 0.922 to 0.951 and 0.856 to 0.909, respectively. CONCLUSIONS: The proposed Vanilla U-Net based model can be used for precise segmentation of masses in MG images. This is because the segmentation process incorporates more multi-scale spatial context, and captures more local and global context to predict a precise pixel-wise segmentation map of an input full MG image. These detected maps can help radiologists in differentiating benign and malignant lesions depend on the lesion shapes. We show that using transfer learning, introducing augmentation, and modifying the architecture of the original model results in better performance in terms of the mean accuracy, the mean DI, and the mean IOU in detecting mass lesion compared to the other DL and the conventional models.

Underwater acoustic sensor networks (UWASNs) have been introduced as a new technology to extract the data for underwater real-time applications such as seismic monitoring, undersea monitoring and control, oil well inspection, military applications, and disaster prevention. This new technology adds more networking capabilities and enables real-time reporting. However, it is restricted to data sensing, forwarding and data transmission. Specifically, transmitting large volumes of data takes a long time and requires a lot of power to be executed. This has inspired our research activities to focus on building an underwater real-time computing system with the minimum execution time and low power consumption. In our research, valuable information is extracted underwater using data mining or compression algorithms. In our previous study, we proposed a set of real-time underwater embedded system (RTUWES) architectures that can handle multiple network configurations. In this study, we extend our research results to develop information extraction algorithms for big data underwater applications to meet real-time constraints. The system performance is assessed in terms of the end-to-end delay and power consumption. We have built a simulator for practical study. The simulation results are presented to demonstrate the performance of our proposed system based on an information extraction algorithm.

Cloud applications can be modeled as workflows. These workflows can be represented as Directed Acyclic Graphs (DAGs) or non-DAGs. A graph shows the relationship between tasks that compose a workflow and the dependencies between them. In this paper, we introduce a method for transforming a workflow application graph into its computational model graph. The generated model provides all possible execution times with their respective probabilities to generate more precise execution time estimates which can be used in better scheduling and resource allocation.

BACKGROUND: The limitations of traditional computer-aided detection (CAD) systems for mammography, the extreme importance of early detection of breast cancer and the high impact of the false diagnosis of patients drive researchers to investigate deep learning (DL) methods for mammograms (MGs). Recent breakthroughs in DL, in particular, convolutional neural networks (CNNs) have achieved remarkable advances in the medical fields. Specifically, CNNs are used in mammography for lesion localization and detection, risk assessment, image retrieval, and classification tasks. CNNs also help radiologists providing more accurate diagnosis by delivering precise quantitative analysis of suspicious lesions. RESULTS: In this survey, we conducted a detailed review of the strengths, limitations, and performance of the most recent CNNs applications in analyzing MG images. It summarizes 83 research studies for applying CNNs on various tasks in mammography. It focuses on finding the best practices used in these research studies to improve the diagnosis accuracy. This survey also provides a deep insight into the architecture of CNNs used for various tasks. Furthermore, it describes the most common publicly available MG repositories and highlights their main features and strengths. CONCLUSIONS: The mammography research community can utilize this survey as a basis for their current and future studies. The given comparison among common publicly available MG repositories guides the community to select the most appropriate database for their application(s). Moreover, this survey lists the best practices that improve the performance of CNNs including the pre-processing of images and the use of multi-view images. In addition, other listed techniques like transfer learning (TL), data augmentation, batch normalization, and dropout are appealing solutions to reduce overfitting and increase the generalization of the CNN models. Finally, this survey identifies the research challenges and directions that require further investigations by the community.

Underwater acoustic sensor networks have emerged as a new technology for underwater real-time applications such as oil inspection, seismic monitoring, and disaster prevention. However, this new technology is bound to data sensing, transmission, and forwarding, which makes the transmission of large volumes of data costly in terms of both time and power. This has inspired our research activities to develop underwater computing systems. In this advanced technology, information is extracted under the water using embedded processors via data mining and/or data compression. In our previous study, we developed a new set of real-time underwater embedded system architectures that can handle various network configurations. The aim was to minimize end-to-end delay and power consumption based on network parameters (i.e., data rate, central processing node capabilities, gathering node capabilities, and water depth) for both homogenous and heterogeneous applications. In this study, we developed a data-gathering algorithm that divides sensor nodes into clusters to find the best location for master nodes and their sensor members and the best location for the central computer. The system performance is calculated in terms of minimum end-to-end delay, power consumption, and load balancing among master nodes. Simulation is used to verify the results and to evaluate the performance of various sensor topologies.

6TiSCH network architecture has recently been introduced to combine the high reliability and low-power consumption of the TSCH (Time-Slotted Channel Hopping) mode of IEEE 802.15.4e MAC with the ease of integration offered by the IP-enabled upper layer protocols. 6TiSCH network uses RPL (Routing Protocol for Low Power and Lossy Networks) as its routing protocol to manage the network layer functionalities. RPL however is vulnerable to internal routing attacks such as Rank attack where a malicious node multicasts a fake position (Rank) or a fake path cost toward the sink node to lure nearby nodes to forward their packets through it. In this paper, we propose a hybrid specification-based intrusion detection system (IDS) that consists of centralized and distributed modules installed on the sink and RPL nodes respectively to prevent nodes from selecting an intruder as their successors. The proposed method also eliminates intruders' chances of becoming a time source and disrupt the synchronization of 6TiSCH networks. The results from our extensive simulations show that compared with existing countermeasures, the proposed IDS can effectively protect RPL topologies while only incurring limited network management overhead.

Underwater sensor networks are bounded by data sensing, transmitting, and forwarding limitations. The transmitting of large volumes of data can require a large amount of time and power. This has led researchers to focus on the new technology of underwater computing systems, in which information is extracted under the water using embedded processors via data mining and/or data compression. In this paper, a set of underwater embedded system (UWES) architectures is developed that can handle different network configurations. These developed architectures have a single processing node and are assumed to be homogenous. An architecture is selected to match a given set of requirements including data rate, processing node capabilities, gathering nodes capabilities, and water depth. Analytical models are developed for each type of architecture, which estimate both end to end delay and power consumption. Simulations that verify the results and evaluate the performance of the architectures are also provided.

Underwater robotic swarms have more challenging operating conditions when compared to their ground counterparts. One such major limitation is vastness of the oceanic environment, which significantly increases the possibility of losing swarm members. Although swarms can tolerate losses, if care is not taken in the design of swarm-level behaviors, they can cause a complete failure of the mission. An additional design factor for such systems is, therefore, the spatial constrained-ness of the swarm. Virtual Tether Search (VTS) has been developed to address this concern. Robots use a virtual tether attached to the drop-off location along with dead-reckoning to stay within a maximum-radius distance from that location. Constrained Spiral Flocking (CSF), a previously developed algorithm, Robotic Particle Swarm Optimization (R-PSO), and Simple Sweeping (SSW) are compared to VTS and pros and cons of each algorithm are highlighted. VTS is shown to have a superior behavior in terms of omni-directionality and loss-prevention at the expense of relatively slow, but guaranteed convergence.

One method of alleviating the burdens of low bandwidth channel in underwater sensor networks (UWSNs) is to perform in-network processing on the collected data, which leads to efficient channel usage, improvement of the end-to-end delay, and improvement of the network lifetime. However, for applications that require large amounts of data, such as seismic monitoring, the detection and tracking of marine objects, and underwater multimedia systems, the use of traditional underwater sensor nodes to perform such data processing techniques is impractical because of their limited power and processing capability. Therefore, the deployment of underwater sensor nodes called processing nodes that have extended power resources and higher features processing units can mitigate the problem of underwater in-network processing. Because the underwater processing nodes are expensive, their deployment is usually considered to be an optimization problem with the objective to best satisfy certain parameters. To solve the optimization problem efficiently, we propose several heuristic approaches that can be used to solve the optimization problem in polynomial time. The quality of the obtained solutions is verified by simulation and compared with the optimal solution.

Real-time embedded systems have become widely used in many fields such as control, monitoring and aviation. They perform several tasks under strict time constraints. In such systems, deadline miss may lead to catastrophic results so that all jobs need to be scheduled appropriately to ensure that they meet their deadline times. This paper presents an efficient dynamic scheduling algorithm during run-time to schedule periodic tasks in multiprocessor environments and uniprocessor as well using a dynamic average estimation. Dynamic average estimation refers to changing in different probability distributions when a task is added or removed from them. It is not always available a value of Worst-Case Execution Time (WCET) in many real-time applications such as multimedia where data has a great variation. The proposed approach selects which task or a set of tasks must be picked up for execution. A simulation system was developed to show validation of the proposed approach.

Identifying the location of a target in an unbounded underwater environment is a challenging task. Limited and intermittent communication only adds to the difficulty of the process. Many target search algorithms use communication as an essential structural component to coordinate Autonomous Underwater Vehicles' (AUV) motion and share sensory information. Multiple algorithms also depend mainly on a sensed gradient to find the target, which is not always available. Sweeping algorithms are generally time and resource consuming and usually cover directional subspaces. Random walk based search suffers from the dispersion problem and does not benefit from the distinguishing features of swarms. To address these concerns, we propose Constrained Spiral Flocking (CSF) search. It uses a self-terminating logarithmic spiral to expand from the drop-off location performing the search, then shrink back, bringing unsuccessful AUVs to the source location. No communication is involved except at the target to attract more AUVs. Flocking is also used to maintain swarming. The algorithm can find the target in any direction, and has a faster convergence for large swarm sizes compared to simple sweeping and random walk.

Underwater sensor networks (UWSNs) have emerged as an essential technology for various undersea applications. However, the use of acoustic links in UWSNs poses critical challenges in terms of overall delay, energy consumption and low bandwidth, which make the transmission of raw data in large sizes impractical. In our previous work, we employed various nodes (processing nodes, gateway nodes, and sensing nodes) that are used to construct different candidate architectures (i.e. single, pipeline, and hybrid of parallel/pipeline). We exploit the idea of in-network data processing in order to reduce the volume of data and extract only valuable information. In this paper, we analytically calculate and compare the performance of the various types of proposed architectures. The tradeoff between the cost of processing and the expected speedup is also analyzed. The results confirm our previous research hypothesis that processing the collected data locally and applying the idea of pipeline/parallel processing leads to significant improvement in the performance of UWSNs.

The ability to estimate performance metrics such as latency (delay) at an early stage of final implementation in any embedded system is essential for efficient design specially realtime systems. Constructing performance models and evaluation techniques of a given system requires a significant effort. This paper presents a mapping scheme between a Functional Modeling Approach such as FSM, UML etc and an Analytical (Mathematical) Modeling Approach such as Hierarchical Performance Modeling (HPM) as a technique to find the expected average delay time for different layers of abstractions. A generic FSM is proposed to be used in order to estimate the expected average delay and to find a bottleneck of a system. A case study is presented to illustrate the concepts of the mapping scheme to estimate the delay and to determine the bottleneck(s).

Large scale missions in unpredictable and unstable underwater environments are beyond the capabilities of a single intelligent and complex robot. Relying on one robot is far from optimal as loss of the unit means failure of the whole mission. On the contrary, robotic swarms depend on large numbers of simple, cheap, and error-prone robots that exhibit global desirable features like fault-tolerance, scalability, and robustness. The study of underwater robotic swarms from the overall mission-planning perspective has been very limited. Planning specific parts of a mission has mostly been the focus of previous research. We propose a general framework for designing and planning underwater swarm missions. We break a typical mission down into its primary constituents and study the requirements for each sub-mission separately. Initially, the swarm self-organizes to form a shape that maximizes residual energy and minimizes water resistance during transport towards the target. This is followed by path planning and shape maintenance, in which the swarm strives to maintain its collective shape and move in cohesion on a collectively-selected path. Next, another self-organization phase takes place to optimize mission-core accomplishment at the target. Remaining phases, in the back trip, are the counterparts of the first two. Related work in each phase is presented and discussed and future work is also highlighted.

Metabolomics is the study of small molecules, called metabolites, of a cell, tissue or organism. It is of particular interest as endogenous metabolites represent the phenotype resulting from gene expression. A major challenge in metabolomics research is the structural identification of unknown biochemical compounds in complex biofluids. In this paper we present an efficient cheminformatics tool, BioSMXpress that uses known endogenous mammalian biochemicals and graph matching methods to identify endogenous mammalian biochemical structures in chemical structure space. The results of a comprehensive set of empirical experiments suggest that BioSMXpress identifies endogenous mammalian biochemical structures with high accuracy. BioSMXpress is 8 times faster than our previous work BioSM without compromising the accuracy of the predictions made. BioSMXpress is freely available at http://engr.uconn.edu/~rajasek/BioSMXpress.zip.

Optimal deployment of multi-surface gateways is a challenging task that has been shown to improve the performance of underwater sensor networks (UWSN). However, the dynamics of both the surface gateways and the underlying sensor deployments can impair the benefits of an initial deployment. In this paper we opt to tackle the dynamics of the underwater environment by adaptive redeployment of the surface gateways. Surface-gateways decide on the timing of the redeployment by keeping track of the transmission power used by nodes during communications. They coordinate their redeployment plan based on the outcome of an optimization algorithm to find the best global solution to minimize the overall transmission power level used by all the nodes in the network. We have used greedy heuristics to solve the optimization problem to cope with processing limitations of UWSN nodes. Our results show that our strategy results in a reduction in the overall energy consumption and the average end to end delay.

Underwater Sensor Networks are associated with a number of applications that require real-time delivery of large data. Examples include: still frame images or full-motion videos in seismic monitoring setups, oil pipe leak detection, and capturing sea activities. However, the transmission of large data relying only on acoustic communication is challenging due to the unique characteristics of aquatic channels, mainly, limited available bandwidth and long propagation delays. In this paper, we advocate a new system architecture called Underwater Sensing and Processing Network (USPN). USPN adopts efficient data processing algorithms to reduce data size and hence improve channel utilization and reduce end-to-end delay. We develop an analytical model for two network scenarios. The first scenario includes a single processing node communicates with a gateway while in the second scenario data are communicated via relay nodes. The objective of our model is to maximize the performance gain in terms of reducing the overall end-to-end delay and power consumption. In addition, we analyze the tradeoff between different objective parameters and the obtained gain. Our results show USPN can maximize the performance gain dramatically.

Traditional Associative Classification (AC) algorithms typically search for all possible association rules to find a representative subset of those rules. Since the search space of such rules may grow exponentially as the support threshold decreases, the rules discovery process can be computationally expensive. One effective way to tackle this problem is to directly find a set of high-stakes association rules that potentially builds a highly accurate classifier. This paper introduces AC-CS, an AC algorithm that integrates the clonal selection of the immune system along with deterministic data sampling. Upon picking a representative sample of the original data, it proceeds in an evolutionary fashion to populate only rules that are likely to yield good classification accuracy. Empirical results on several real datasets show that the approach generates dramatically less rules than traditional AC algorithms. In addition, the proposed approach is significantly more efficient than traditional AC algorithms while achieving a competitive accuracy.

The performance of Underwater Sensor Networks (UWSNs) can be severely affected by the dynamics of underwater environment. A surface sink is usually deployed at a pre-specified location to maximize one or more performance metrics. However, when the network is dynamic, a redeployment of surface sink should be considered to reduce the effect of mobility on the network performance. Redeployment can be done periodically, at times based on a mobility prediction models, or adaptively based on performance degradation. Unnecessary redeployment can result from using the periodic or prediction based redeployment. In this paper we present an adaptive dynamic sink redeployment strategy that enforces redeployment only if a reduction in energy consumption is guaranteed. The redeployment decision is based on routing information collected at the surface sink throughout network operation. We use a location unaware routing protocol “adaptive power controlled routing protocol” as the underlying routing strategy. When the mobility of the network is not severe, nodes tend to use a fixed power level to communicate with neighboring nodes or surface sink. However, if more nodes are switching to use higher power levels for communication and the energy consumption is increased a sink redeployment procedure is started. Surface sink then triggers localization and finds the optimal new location of surface sink to minimize total energy consumption. Simulation results show that adaptive sink redeployment achieves a considerable reduction in energy consumption.

Solving Partial Differential Equations (PDEs) is very important in many areas. Since PDE solvers take very long time for numerous applications of interest, we need efficient parallel implementations. An attractive parallel computing platform that is widely used at present is the Graphics Processing Unit (GPU). In this paper we present an efficient technique that uses the red-black Gauss-Seidel method to solve PDEs. This technique allows the efficient use of the relatively larger register file available in each Streaming Multiprocessor (SM), as well as the shared memory. It also allows the communication between the threads of a block. We employ the red-black Gauss-Seidel method, in this paper, to solve the 2D steady state heat conduction problem on two different GPUs. An overall speedup of 484 relative to the CPU sequential implementation is achieved. A speedup of about 2.6 relative to Foster's GPU implementation on the same GPUs is also achieved.

Research in science and engineering has resulted in the generation of voluminous datasets. For instance, biological databases such as PubMed now have millions of articles. Given this growth in data, the problem of retrieving information relevant to a specific topic has become a big challenge. In this paper we focus on the problem of retrieving articles pertaining to a given topic from among a huge collection of articles. In particular, we investigate the problem of classifying articles. Though numerous techniques and tools are available for documents classification, a shortcoming in them is that they take too much time. In this paper we present generic computational techniques that can classify articles efficiently. Our algorithms are based on algorithms that have been proposed for a related problem called gene selection. Gene selection is the problem of identifying a minimum set of genes that are responsible for certain events (for example the presence of cancer). Even though gene selection was originally proposed for biological data analysis, the technique itself is generic. For example, `genes' can be thought of as generic variable. A typical tool that we envision will take as input a set of keywords (that characterize the information of interest) and will develop a learner that will identify a small subset of the keywords that are capable of classifying papers into two types. A paper is of the first type if it has information of interest and a paper is of the second type if the paper does not have information of interest. Experiments show that the new algorithm obtains a higher classification accuracy using a smaller number of selected keywords when compared to one of the best algorithms reported in the literature.

In underwater wireless sensor networks (UWSNs), one efficient way to alleviate the burdens of high propagation delay and high error probability during transmission is to deploy surface-level gateways, which utilize radio waves to forward information to a control station. Usually, deployment of the gateways is considered as an optimization problem with the objective to best satisfy certain parameters. In this work, we propose a prediction assisted dynamic surface gateway placement algorithm for mobile underwater sensor networks, called “PADP”, which intends to maximize the coverage within a specific period of time. PADP applies a tracking scheme “IMM” to predict sensor nodes' positions, adopts branch-and-cut to solve the optimization problem, and employs a disjoint-set data structure to handle connectivity. Simulation results show that PADP outperforms the existing static gateway deployment scheme.

The N-FINDER algorithm is widely used for endmember extraction from hyperspectral images. One of the disadvantages of N-FINDER is that its sequential implementations have long run times due to their relatively large computational complexity. A fast parallel version of N-FINDER is developed in this paper. This version combined with the use of Hyperspectral Image Reduction for Endmember Extraction technique (HIREE) provides an algorithm that is 8 times faster than the original N-FINDER sequential algorithm.

Estimating the criticality of each link in a transportation network is a crucial step for guiding the design and deployment of vulnerability reduction measures. Using exhaustive simulations based on user-equilibrium assignment to evaluate the effect of the failure of each link (or set of links) can be prohibitively time-consuming for reasonably-sized transportation networks. In this paper, we propose an alternative heuristic approach to the estimation the vulnerability of network links employing efficient graph-theoretical algorithms. In particular, our model estimates the cost of single link failure based on the increase in shortest path travel time taking into account the effect of congestion. Results show that the proposed method can reliably be used to estimate the relative effect of each link failure on the system travel time and rank links accordingly.

In this paper we study the important problems of message routing, sorting, and selection in a radio network. A radio network consists of stations where each station is a hand-held device. We consider a single-hop radio network. In a single-hop network it is assumed that each station is within the transmission range of every other station. Let RN(p; k) stand for a single-hop network that has p stations and k communication channels. The problems of sorting and selection have been studied on RN(p; k). For these problems it is assumed that there are n/p elements to start with at each station. At the end of sorting, the least n/p elements should be in the first station, the next smallest n/p elements should be in the second station, and so on. The best known prior algorithm for sorting takes 4n/k +o(n/k) broadcast rounds on a RN(p; k). In this paper we present a randomized algorithm that takes only 3n/k +o(n/k) broadcast rounds with high probability. For the selection problem, it is known that the maximum or minimum element can be found in O(log n) rounds on a RN(n; 1), provided broadcast conflicts can be resolved in O(1) time. The problem of general selection has not been addressed. In this paper we present a randomized selection algorithm that takes O(p/k) rounds on a RN(p; k) with high probability. An important message routing problem that is considered in the literature is one where there are n/p packets originating from each station and there are n/p packets destined for each station. The best known routing algorithms take nearly 2n/k times slots. An important open question has been if there exist algorithms that take only close to n/k time slots. Note that a trivial lower bound for routing is n/k. The existence of such algorithms will be highly relevant especially in emergencies and time critical situations. In this paper we answer this question by presenting a randomized algorithm that takes nearly n/k time slots with high probability.

Network lifetime is often a crucial measure of the cost-effectiveness of underwater wireless sensor networks and a guiding factor of their deployment. In this paper, we propose a placement strategy for surface gateway nodes in order to maximize network lifetime under a given set of functional requirements. We formulate the problem as an optimization problem and solve it for sample networks. Results show a trade-off between lifetime and other performance metrics, such as average end-to-end delay. We propose a multi-objective reformulation of the problem to strike the required balance between performance and lifetime.

Formal grammars have been employed in biology to solve various important problems. In particular, grammars have been used to model and predict RNA structures. Two such grammars are Simple Linear Tree Adjoining Grammars (SLTAGs) and Extended SLTAGs (ESLTAGs). Performances of techniques that employ grammatical formalisms critically depend on the efficiency of the underlying parsing algorithms. In this paper, we present efficient algorithms for parsing SLTAGs and ESLTAGs. Our algorithm for SLTAGs parsing takes O(min{m,n⁴}) time and O(min{m,n⁴}) space, where m is the number of entries that will ever be made in the matrix M (that is normally used by TAG parsing algorithms). Our algorithm for ESLTAGs parsing takes O(min{m,n⁴}) time and O(min{m,n⁴}) space. We show that these algorithms perform better, in practice, than the algorithms of Uemura et al.

The Cell Broadband Engine (CBE) is a heterogeneous multi-core processor with unique design properties for high-performance computing. It consists of one power processing element (PPE) and eight synergistic processing elements (SPEs) connected with the elements interconnect network (EIB). It employs some novel techniques, such as software managed cache, to hide memory latency and guarantees, by default, maximum utilization for the overall system resources. However, utilization of these facilities requires complex designs and implementations of algorithms to get the best performance. In this paper we discuss our micro-threading model realized by a nano-kernel implemented on top of each SPE. SPE's Nano-kernel, or SPENK, employs the micro-threading model to increase CBE resources utilization while simplifying the programming model. Our framework boosted the processor's overall performance by a factor of five compared to the current threading model. It allowed us to build a distributed model for SPEs' tasks management and automated local storage (LS) management. We tested our framework on two types of algorithms: (1) uniform memory access algorithms, such as parallel summation, and (2) Non-uniform or irregular memory access algorithms, specifically the parallel tree spanning algorithm. We have also investigated the optimal parameterization of micro-threads on each SPE to automatically reach the best possible performance. Using proper parameterization of micro-threads, we could achieve three to fivefold performance improvement.

Deploying radio-capable gateways at the sea surface can mitigate the limitations of acoustic communications in underwater sensor networks (UWSN). Finding the best placement for gateways is formulated as an ILP problem. The choice of gateway candidate locations can affect both the feasibility and the quality of the solution. In this paper, we show the limitation of using a regular mesh of candidate locations, and present a novel algorithm for defining candidate locations that both reduces the complexity of the optimization problem and enhances the feasibility and quality of the solution.

There have been a large number of projects based on the Distributed Object Oriented (DOO) approach for solving complex problems in various scientific fields. The Mismatch problem is one of the most important problems facing the DOO system, where the initial design of the DOO application does not give the best class distribution. In such a case, the DOO software may need to be restructured. In this paper, we propose a methodology for efficiently restructuring the DOO software classes to be mapped on a distributed system consisting of a set of nodes. The proposed methodology consists of two phases. The first phase introduces a recursive graph clustering technique to partition the OO system into subsystems with low coupling. The second phase is concerned with mapping the generated partitions to the set of available machines in the target distributed architecture. A simulation evaluation was carried out for a set of randomly generated DOO software designs. Then the results were compared with those of the K-Partitioning algorithm in terms of the overall inter-class communication cost.

Deploying multiple surface-level radio-capable gateways enhances the performance of underwater acoustic sensor network. The locations of gateways have to be carefully selected to maximize the benefit in a cost-effective way. In this paper, we show how to efficiently solve the surface gateway deployment optimization problem, using heuristic approaches. The results of applying these proposed algorithms to a variety of practical deployment scenarios suggest that these heuristics are nearly optimal for practical cases.

The problem of sorting has been studied extensively and many algorithms have been suggested in the literature for the problem. Literature on parallel sorting is abundant. Many of the algorithms proposed, though being theoretically important, may not perform satisfactorily in practice owing to large constants in their time bounds. The algorithms presented in this paper have the potential of being practical. We suggest some novel sorting mechanisms specific to the cell broadband engine. We try to utilize the specifics of its architecture in order to get the optimum performance. As part of our comparative analysis we juxtapose these algorithms with similar ones implemented on Itanium 2 processor as well as the Pentium 4 processor.

Scheduling real-time task graphs on cluster platforms requires efficient utilization of the cluster's resources in order to satisfy the deadlines of the tasks. In this paper, we introduce a new approach to schedule real-time tandem task graphs on a computer cluster. Our approach aims at minimizing the communication time needed to transfer data among the cluster's nodes respecting all the limitations imposed by cluster's network (e.g., limited connectivity of the network topology and limited bandwidth of the communication links). This communication time represents an extra overhead that is added to the execution time of the tasks; hence, an additional processing power is needed to satisfy tasks' deadlines. Minimizing this communication time helps utilize the processing power of the cluster's processors efficiently, and consequently minimize rejection rate of the tasks. We evaluate the performance of our approach through a set of simulation experiments running on heterogeneous cluster environments. The results show that our approach considerably improves acceptance rate of the applications on the cluster.

We study the effects of bursty Internet traffic through simulations. Both short-range dependency (SRD) traffic and long-range dependency (LRD) traffic are simulated over different burst parameters. The results are collected for 10 different 24 hour simulated periods in order to study and measure day-to-day statistical fluctuation. Effects of employing different traffic admission constraints are examined. An alternative for improving network throughput and utilization is proposed. Finally, a case when arrival patterns of traffic are correlated is explored.

Cluster computing systems are currently used to execute high performance applications that exhibit real time characteristics. A high-speed communication networks are used to interconnect the nodes of a cluster. Also, special software is used to allocate and manage the execution of the parallel tasks of the applications on cluster's processors to satisfy real-time requirements and achieve high throughput. In this paper, we present a new algorithm to allocate tasks’ workloads in a way that improves the utilization of each cluster's processor. Consequently, a cluster's processor can accept more tasks and results in higher throughput. The idea of the algorithm depends on assigning a variable processing power to the task under consideration to satisfy its deadline instead of rejecting it if a constant processing power cannot be guaranteed. Simulation results reveal that the acceptance rate of submitted tasks to a cluster's processor using the new approach is superior to previous approaches.

Improper scheduling of real-time applications on a cluster may lead to missing required deadlines and offset the gain of using the system and software parallelism. Most existing scheduling algorithms do not consider factors such as real-time deadlines, system reliability, processing power fragmentation, inter-task communication and degree of parallelism on performance. In this paper we introduce a new scheduling algorithm, which is based on using an objective function to guide the search for a near optimal solution. This objective function includes different criteria such as real-time deadlines, reliability, and quantitative measures of the communication, degree of parallelism and processing power fragmentation. The presence of different criteria may affect the overall acceptance rate of the applications. We also investigate the effect of reliability on the overall acceptance rate.

In end-to-end monitoring, traffic measurements are recorded at the source and destination nodes. In QoS distribution monitoring, the measurements are recorded at several intermediate nodes along a connection. End-to-end monitoring is conceptually simple and easy to implement, but not capable of localizing the degradation. Thus, any corrective action has to be applied end-to-end, which can be prohibitively expensive. Although QoS distribution monitoring holds the promise of being able to localize the degradation to a single domain, prevalent QoS distribution monitoring techniques do not consistently provide this capability. They also consume excessive resources in the monitoring process and rely on assumptions which are unlikely to hold in practice. In this paper we describe the design tradeoffs associated with QoS distribution monitoring and highlight the limitations of the existing research. We then describe a QoS distribution monitoring scheme which provides practical solutions to these challenges. Using extensive analysis we compare the efficiency of the proposed scheme to the prevalent ones.

In systems where job service demands are only known probabilistically, there is very little to distinguish between jobs. Therefore, no universal optimum scheduling strategy or algorithm exists. If the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. In a detailed discrete event simulation, we have explored the use of this function for increasing the probability that a job will meet its deadline. We have tested many different distributions with a wide range of sigma2and shape, four of which are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. We also studied the use of two slow servers versus one fast server, and have found that they provide comparable performance, and in a few cases the double server system does better

Summary form only given. In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling parallel and distributed systems. However, they have their limitations. In particular, the product-form solution of Jackson networks assumes steady state and exponential service centers or certain specialized queueing disciplines. We use a transient model studying distributed systems with finite workload (no new arrivals). Using some nonexponential distributions we show to what extent the exponential distribution can be used to approximate other distributions. When the number of tasks to be executed is large enough, the model approaches the product-form solution in those cases where the Jackson networks can be applied. We also study some cases where Jackson networks can't be applied (the nonexponential servers have queueing). The model can be used for reliability analysis of systems that allow failures without repair (fail-stop).

Efficient task scheduling is essential for achieving high performance computing applications for distributed systems. Most of existing real-time systems consider schedulability as a main goal and ignores other effects such as machines failures. In This work we develop an algorithm to efficiently schedule parallel task graphs (fork-join structures). Our scheduling algorithm considers more than one factor at the same time. These factors are scheduability, reliability of the participating processors and achieved degree of parallelism. To achieve most of these goals, we composed an objective function that combines these different factors simultaneously. The proposed objective function is adjustable to provide the user with a way to prefer one factor to the others. The simulation results indicate that our algorithm produces schedules where the applications deadlines are met, reliability is maximized and the application parallelism is exploited.

Scheduling can require analyzing not only the total computation time of a task, but also the remaining execution time, R(t)/sub /spl Delta/t/, after accumulated time /spl Delta/t. Often a software program's execution time is characterized by a single value (mean). When scheduling is based on partial execution (a common scenario in multimedia systems) a more accurate estimation of remaining time (R(t)/sub /spl Delta/t/) is desired than can be obtained from just the initial mean value, in order to have effective scheduling decisions. The remaining time approach can provide more accurate estimation, and therefore more effective scheduling, in time-sensitive situations. We developed an analytical model for computing expected remaining execution time, (R(t)/sub /spl Delta/t/)~ , of software programs from their execution time and probability distributions. To implement the equations, we further designed an algorithm that computes (R(t)/sub /spl Delta/t/)~ for operating system scheduling applications. We proved that the real time execution complexity of the algorithm is O(1) and is, therefore, independent of the size of the distribution. Our method of more accurate estimate of (R(t)/sub /spl Delta/t/)~ implies expect better scheduling performance in applications where remaining execution time is used, especially in CPU scheduling.

Caching frequently asked queries is an effective way to improve the performance of both centralized and distributed database systems. Intensive works have been done in this area to propose different query caching techniques and to evaluate their performance. However, most of these works were confined to caching previous query results in a single-level caching architecture. Evaluations of these works were based on simulations. In [D.S. Elzanfally et al., 2003], we proposed a new query caching technique for caching both query results and execution plans in a multilevel caching architecture. The centralized version of this technique was evaluated and the results were reported in [D.S. Elzanfally et al., 2003]. In this paper, we present an analytical model to evaluate the performance of the proposed technique in distributed database systems.

Each computer system in operation today is certain to experience faults in its operational lifetime. There is more than one source, which can cause faults, for example environmental factors, communication, interaction with users, or hardware or software design flaws randomly build into the system. A reliable system is the one that would continue operation albeit in a degraded mode despite the presence of faults. In this paper, we introduce an efficient method to schedule a tandem of real-time tasks in cluster computing with possible processor failures. The method is based on developing an objective function that combines different scheduling goals. This objective function is used to guide the search algorithm to find an efficient solution. The proposed algorithm consists of three terms, reliability, deadline and tasks grouping to minimize remote communication among tasks. The proposed method creates a scheduling table based on the objective function then searches this table for a feasible solution. The method is efficient because it reduces communication between different tasks by grouping them together. This grouping process reduces application de-fragmentation as well.

Scheduling a large number of high performance computing applications on a cluster-computing environment is a complex task. This becomes more critical in real time systems. Efficient scheduling strategies are critically important to achieving good performance. A cluster scheduler without enough knowledge of the state of the cluster and the scheduled tasks cannot adequately manage the cluster resources. Accordingly, the available processing power of the participating nodes may experience uncontrolled fragmentation. Thus, some of the submitted applications may be rejected due to tasks missing their deadlines. The literature on scheduling real-time task graphs is much less extensive, especially for providing timing guarantees while maximizing the processing power utilization. In this paper, we present a framework for allocating and scheduling real-time applications represented as parallel task graphs on a cluster. We utilize the available processing power on each processor to accommodate as many tasks as possible while satisfying the required deadline of each task. The algorithm also reduces the communication cost among tasks and the possibility of processing power fragmentation.

Controlled-load service that provides acceptable quality of service to adaptive real-time applications without making absolute guarantee is extensively considered, owing to its higher resource utilization than guaranteed service. Enhancement of utilization strongly relies on traffic scheduling method adaptable to a varying traffic load, and admission control algorithms that do not depend on worst-case traffic behavior. We propose a new scheduling scheme called delay-synchronized dynamic priority (DSDP), which exploits node synchronization of a multi-hop network by dynamically altering the priority of a packet to offset the deviation from its expected arrival time. Additionally, we develop a measurement-based admission control algorithm that uses existing traffic measurements under the DSDP scheme for controlled-load service.

A methodology and related software design environment for the development of performance-engineered object-oriented distributed systems is essential. In this research, a performance-engineered design framework that utilizes the system architecture and object-oriented software design techniques of the Unified Modeling Language (UML) and the architecture of the Hierarchical Performance Model (HPM) is developed to assist designers in evaluating alternatives for performance enhancement. The developed framework integrates the architectural, structural and behavioral components of an application with the performance parameters required for performance model generation and evaluation during the software design process. Performance views for the presentation of performance information and selection of critical path scenarios along with an example are briefly described.

Performance modeling and evaluation techniques are essential when designing and implementing distributed software systems. Constructing performance models for such systems can require significant effort. This paper presents Hierarchical Performance Modeling as a technique to model performance for different layers of abstraction. Once the system architecture and software functionality have been specified, this model supports performance model generation for the evaluation and analysis of computation delays of software processes, communication delays of distributed software architectures, and hardware platform alternatives. A simplified example is presented to illustrate the concepts of the Hierarchical Performance Model.

We study the architectural impact of the I/O subsystem design on the performance of high-speed networks. We developed a new architecture for this I/O subsystem. The new architecture resolves the "windowing out" and the "delayed acknowledgment" problems that are raised in the current architectures. It also speeds up the receiver's absorbing process and improves the network utilization and its throughput.

Under a shared memory environment, processes in a parallel structure communicate with one another by shared variables. Since no two processes should access shared variables simultaneously, they should be placed in the critical section to guarantee mutually exclusive access. The problem is how to order processes competing to access the critical section with the aim of minimizing the time spent to execute these processes. Previously, a heuristic algorithm scheduled these processes without allowing preemption in accessing the critical section. We present another heuristic algorithm with the preemption approach to improve previous results.

Many Arabic character recognition systems have been proposed since the early eighties. Most systems reported high recognition rates, however, they overlooked a very important factor in the process; the speed factor. A parallel Arabic character recognition system is introduced. The goal of the system is to achieve both full accuracy and high speed. This has been accomplished by integrating the character recognition process with parallel processing and distributed computing concepts. Experimental results showed that the multi-processing environment is very promising in enhancing a sequential Arabic character recognition system performance.

A modeling approach for parallel structures (PSs) is introduced based on the processor-time (P-T) diagram (Gantt chart). The key features are that design requirements are represented as work required, individual and collective module designs as work accomplished, and resource utilization as work wasted. These representations are given simple geometric interpretations in the P-T diagram, making analysis of deterministic models an exercise in algebra. Next, performance parameters are derived which are provably ideal and can be used with profit for comparing competing designs or the quality of a particular design in terms of its execution time and use of resources. Then the authors describe the application of these performance measures to develop an efficient parallel structure.

The focus of this paper is to present the results of our investigation and evaluation of various shared-memory parallelizations of the data association problem in multitarget tracking. The multitarget tracking algorithm developed was for a sparse air traffic surveillance problem, and is based on an Interacting Multiple Model (IMM) state estimator embedded into the (2D) assignment framework. The IMM estimator imposes a computational burden in terms of both space and time complexity, since more than one filter model is used to calculate state estimates, covariances, and likelihood functions. In fact, contrary to conventional wisdom, for sparse multitarget tracking problems, we show that the assignment (or data association) problem is not the major computational bottleneck. Instead, the interface to the assignment problem, namely, computing the rather numerous gating tests and IMM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the assignment problem), is the major source of the workload. Using a measurement database based on two FAA air traffic control radars, we show that a "coarse-grained" (dynamic) parallelization across the numerous tracks found in a multitarget tracking problem is robust, scalable, and demonstrates superior computational performance to previously proposed "fine-grained" (static) parallelizations within the IMM.

Abstract Definition of a software process to be analyzed is normally top‐down. Analysis starts with a rough description and evolves into finer granularity as more performance and functional requirements become available. This process involves different performance models at each stage. The relationship between these models forms a hierarchy of performance models. Performance parameters propagate bottom‐up and the analysis of these models is very complex, so that it is essential to develop computer aided performance evaluation (CAPE) tools to support the evaluation process. In this work, we developed a graphical interface for CAPE environments called the GRAphical Performance Evaluation (GRAPE) system. GRAPE supports the structural design of five different performance models: queueing, state, computation structure, data flow and statistical models. These models can be used to design parallel/distributed real‐time software systems at different levels of granularity. GRAPE is the front‐end tool for a CAPE environment that will allow the user to integrate the relationships between different performance metrics at different levels of analysis. These metrics propagate between the modeling hierarchy to arrive at a final quantitative or symbolic measure of its performance.

The authors investigate the modeling and analysis of time cost behavior of parallel computations. It is assumed parallel computations reside in a computer system in which there is a limited number of processors, all the processors have the same speed, and they communicate with each other through a shared memory. It has been found that the time costs of parallel computations depend on the input, the algorithm, the data structure, the processor speed, the number of processors, the processing power allocation, the communication, the execution overhead, and the execution environment. The authors define time costs of parallel computations as a function of the first seven factors as listed. The computation structure model is modified to describe the impact of these seven factors on time cost. Techniques based on the modified computation structure model are developed to analyze time cost. A software tool, TCAS (time cost analysis system), that uses both the analytic and the simulation approaches is designed and implemented to aid users in determining the time cost behavior of their parallel computations.>

Abstract In this paper, we present a software system, OPAS (Optimal Allocation System), that incorporates the optimal allocation policy in the analysis of the time‐cost behaviour of parallel computations. OPAS assumes that the underlying system which supports the executions of parallel computations has a finite number of processors, that all the processors have the same speed and that the communication is achieved through a shared memory. OPAS defines the time cost as a function of the input, the algorithm, the data structure, the processor speed, the number of processors and the processing power allocation. In analysing the time cost of a computation, OPAS first uses the optimal allocation policy that we developed previously to determine the amount of processing power each node receives and then derives the computation's time cost. OPAS can evaluate different time‐cost behaviours, such as the minimum time cost, the maximum time cost, the average time cost and the time‐cost variance. It can also determine the speed‐up and efficiency, and plot the time‐cost curve and time‐cost distribution.

A model is presented for estimating the average response time of parallel programs. It is assumed that the underlying system has a number of processors and all the processors have the same speed. The system is represented as a state transition diagram in which each state represents the number of processes in the system. A state transition can occur in every Delta t time units. If the system has U processors and i processes, each process will receive Delta t*min (1,U/i) processor time before the number of processes in the system changes. A process is terminated when it receives the required processor time. A program leaves the system when all the corresponding processes are terminated. Methods based on the model are developed to estimate the average response time. Several examples are given to demonstrate these methods.>

The design of a high-performance complex software system is discussed. An approach called the spreadsheet performance approach (SPA) is presented that integrates a hierarchy of performance models at different levels. A methodology that uses this approach to design high-performance software systems is also defined. Finally, an example is investigated to show how the approach and the methodology can be applied.>

A software experimental analysis approach that unifies static and dynamic techniques is presented. The goal was to develop practical means to obtain precise, in-depth, and relevant performance information, especially execution time, for guiding design decisions. First, computation cost functions of a program are derived. This is done by modeling the program using the computation structure model and then applying a flow analysis technique to derive the program's cost function. In addition, program instrumentation techniques are employed to measure control flows and to trace program variables. Finally, precise execution-time information is computed by evaluating the cost function against the measured control flows. The three classes of parameters (execution time, control flow and program variables) can be analyzed selectively and interactively; this gives much insight about an individual design alternative's actual behavior. To cope with tedious and frequent analyses of large and complex software, a tool COPES, was built that automates the static and dynamic techniques required. The implementation and usage of this tool are illustrated.>

An architecture assessment environment is proposed for the design and performance evaluation of massively parallel real-time systems. Included are the major inherent phases of design activity and performance analysis that are implicit in the real-time design process. The major contribution is the definition of a comprehensive methodology and corresponding software support tools to allow and assist a designer in his/her development and assessment of parallel real-time systems. Included in the formulation is the ability to specify either homogeneous or heterogeneous hardware architectures, and to provide a basis for determining performance estimates early in the design process which could allow and direct intelligent design decisions. In addition, the methodology presented can be used to support the entire system life-cycle.>

HyperCard is an object-oriented, graphic programming language developed by Apple Computer Inc. for its Macintosh computers. A description is given of the use of HyperCard in the development of prototype human-computer interfaces for CASE systems. Direct manipulation creating static graphic components and artificial delays, are discussed.>

An integrated analysis framework is presented which consists of a hierarchy of models and analysis techniques that can be applied at different levels of the design of distributed computations. The goal is to determine a computation response time as viewed by a user and show how a software's response time can be affected by properties of the underlying communication subnetwork. The result of the computation structure analysis is applied to a buffer processing system and it is shown that transient variations in communication network parameters can shift the execution of a computation from a stable operating region, where execution time cost remains acceptable, to an unstable state.>

A technique for deriving the time cost of parallel computations is presented. The technique is based on reducing the given parallel computation into a sequential one and then applying one of the available techniques developed for sequential computations to derive the required time cost. The reduction process is done by replacing each parallel structure in the given computation with a single operation node whose time cost equals the time cost of the structure. Five categories of parallel structures are identified and the time cost of each is estimated. The technique is then written in an algorithmic form.>

Abstract In this paper, we present a software tool, RTS (real time simulator), that analyses the time cost behaviour of parallel computations through simulation. It is assumed in RTS that the computer system which supports the executions of parallel computations has a limited number of processors all processors have the same speed and they communicate with each other through a shared memory. In RTS, the time cost of a parallel computation is defined as a function of the input, the algorithm, the data structure, the processor speed, the number of processors, the processor power allocation, the communication and the execution environment. How RTS models the time cost is first discussed in the paper. In the model, a locking technique is used to manipulate the access to the shared memory, processing power is equally allocated among all the operations that are currently being performed in parallel in the computer system, and the number of operations in the execution environment of a parallel computation changes from time to time. How RTS works and how the simulation is used to do time cost analysis are also discussed.

As interactive computing has developed, a more comprehensive design methodology is required to produce high-performance software. To achieve this goal, consideration of user performance must be included as an integrated part of the development process. An approach that allows a software engineer to integrate user performance as a design dimension in interactive software system design is presented. This approach is used to study the design of a text editor.>