Power network disruptions triggered by weather events, malfunction, sabotage, or other phenomena can leave harrowing effects on communities. Microgrids with distributed energy resources have the potential to enable swift localized restoration following the interruption of utility power. However, because of the limited generation and storage capacity of microgrids, service restoration will require prioritizing critical load and optimality of operations to render relief to those in dire need. Moreover, this essentially requires fair energy allocation, trust-free energy exchanges, and the integrity of transactions. This paper proposes a consortium blockchain-based energy sharing approach for service restoration using energy crowdsourced through donation or trade. The proposed approach provides a framework that utilizes microgrids’ supply situation and reputation as consortium admission criteria for optimizing the energy cost of blockchain operations. The proposed approach uses a measure called proof of welfare (PoWel), which solves the rationing problem to produce an energy allocation block. Accordingly, it proposes an algorithm by utilizing weighted rationing for prioritizing critical load restoration and an evolutionary optimization algorithm for maximizing social welfare and minimizing power losses. The winner block selected through consensus intrinsically preserves the network stability while conforming to resource and stability constraints. An extensive performance and security analysis ascertain the effectiveness of the proposed approach.

Collaborative Intrusion Detection System (CIDS) protect large networks against distributed attacks. However, a CIDS is vulnerable to insider attacks that decrease the mutual trust among the CIDS nodes. Most existing trust management approaches rely on a central authority, trusted third parties or network peers for managing trust. The current techniques are prone to high false positives and vulnerable to various reputation attacks. For instance, device attestation manages trust among CIDS nodes by verifying the integrity of a node’s hardware and software configuration. However, it lacks real-time monitoring of the dynamic state, limiting its effectiveness against ongoing attacks and malware. Therefore, incorporating the system’s dynamic state in the trust framework is crucial, but it causes false positives requiring corrective mechanisms. To address these challenges, this paper proposes a blockchain-based integrated trust management framework for CIDS, incorporating the device’s genome attestation, the system’s dynamic parameters, and a false positive resilient reputation mechanism. By storing the reputation scores on the blockchain, the framework alleviates the need for a third party for trust management and thus mitigates attacks applicable to reputation-based systems. The paper performs a comprehensive security and performance analysis of the proposed framework to gauge its efficiency and study the effects of a penalty on a node’s reputation during the recovery and rally phases. We also study the impact of false positives on the reputation of a node. The results show that Hyperledger Fabric offers lower transaction latency and low CPU utilization compared to Ethereum Blockchain.

Online learning updates models incrementally with new data, avoiding large storage requirements and costly model recalculations. In this paper, we introduce “OLR-WA; OnLine Regression with Weighted Average”, a novel and versatile multivariate online linear regression model. We also investigate scenarios involving drift, where the underlying patterns in the data evolve over time, conduct convergence analysis, and compare our approach with existing online regression models. The results of OLR-WA demonstrate its ability to achieve performance comparable to the batch regression, while also showcasing comparable or superior performance when compared with other state-of-the-art online models, thus establishing its effectiveness. Moreover, OLR-WA exhibits exceptional performance in terms of rapid convergence, surpassing other online models with consistently achieving high r2values as a performance measure from the first iteration to the last iteration, even when initialized with minimal amount of data points, as little as 1% to 10% of the total data points. In addition to its ability to handle time-based (temporal drift) scenarios, remarkably, OLR-WA stands out as the only model capable of effectively managing confidence-based challenging scenarios. It achieves this by adopting a conservative approach in its updates, giving priority to older data points with higher confidence levels. In summary, OLR-WA’s performance further solidifies its versatility and utility across different contexts, making it a valuable solution for online linear regression tasks.

Exorbitant energy expenses can supersede data center profits. Electricity prices often vary across the geographic regions, caused by gaps in the supply-demand, time of use, and production cost factors. Geo-distributed cloud data centers facilitated by a smart grid and enabled by cloud computing can potentially utilize the spatiotemporal diversity of energy prices to reduce operational expenditure and maximize profit. In this article, we solve the data center profit by formulating it as a constrained multi-objective optimization problem. The proposed solution utilizes an evolutionary algorithm-based higher-level heuristic that optimizes data center revenue and expense objectives simultaneously. The proposed technique provides system managers with trade-off solutions suited to varied operational scenarios. Ours is a multi-step approach, utilizing the optimization scheme to obtain Pareto optimal solutions for the request dispatch and resource allocation problem. When broadly evaluated against a comparative resource optimization scheme, our technique increases revenue while lowering expense and collectively yields a higher profit. It exhibits such performance over a broad range of price changes regardless of the data center's size and utilization level. The extensive simulation results ascertain the effectiveness of the proposed approach across a myriad of system parameters.

Natural hazards and technical malfunctions can cause widespread outages of power networks, adversely affecting communities and infrastructures. Microgrids with distributed generation and storage can help mitigate some of these devastating effects. However, not many communities and infrastructures have alternative power mechanisms. When needed, microgrids may help needy neighbors or critical communities, such as hospitals, by donating or trading surplus capacity. Energy donation in a smart grid is a viable and highly effective restoration option to mitigate the effects of a disaster. However, because of the limited capacity of microgrids, service restoration requires prioritizing critical load and optimality of operations for rendering relief to those in dire need. In this paper, we propose a new framework for enabling energy donation in a smart grid during a crisis when the main supply is cut off. The proposed technique allocates energy using weighted and optimized rationing approaches. It does so by catering to the load critically and users’ historical contribution during restoration. The proposed method is based on an algorithm which employs evolutionary optimization technique that maximizes social welfare and minimizes losses while satisfying the resource and network constraints. Extensive simulation results ascertain the effectiveness of the proposed approach across a myriad of system parameters.

Superpixel-based Higher-order Conditional Random Fields (CRFs) are effective in enforcing long-range consistency in pixel-wise labeling problems, such as semantic segmentation. However, their major short coming is considerably longer time to learn higher-order potentials and extra hyperparameters and/or weights compared with pairwise models. This paper proposes a superpixel-enhanced pairwise CRF framework that consists of the conventional pairwise as well as our proposed superpixel-enhanced pairwise (SP-Pairwise) potentials. SP-Pairwise potentials incorporate the superpixel-based higher-order cues by conditioning on a segment filtered image and share the same set of parameters as the conventional pairwise potentials. Therefore, the proposed superpixel-enhanced pairwise CRF has a lower time complexity in parameter learning and at the same time it outperforms higher-order CRF in terms of inference accuracy. Moreover, the new scheme takes advantage of the pre-trained pairwise models by reusing their parameters and/or weights, which provides a significant accuracy boost on the basis of CRF-RNN [25] even without training. Experiments on MSRC-21 and PASCAL VOC 2012 dataset confirm the effectiveness of our method.

Recently, microRNAs were found to have potential as both diagnostic biomarkers and therapeutic targets for lung cancer, especially in identifying early-stage cancer. However, a miRNA biomarker derived from the standard normal v.s tumor differential expression analysis is not robust, as its functional interactions with messenger-RNA targets may change between different lung cancer subtypes. Furthermore, as evidence suggests miRNA dysregulations and synergistic regulations are important to understanding many cancer diseases, it is important to consider the changes in miRNA-target associations among different lung cancer subtypes. We proposed a pipeline to identify miRNA synergistic modules with high context-specific functional similarity by constructing the MicroRNA Dysregulational Synergistic Network (MDSN). Then, we incorporated the extracted miRNA modules as prior knowledge to a Sparse Group Lasso classifier for more relevant selection of microRNA biomarkers, thereby improving classification results. We applied the method to the TCGA Lung Adenocarcinoma dataset and found extracted miRNA modules from independent subtypes differential analyses to have high agreement with known miRNA family assignments. Cross-validation test also demonstrates clustering miRNAs by considering the dysregulation between miRNAs and its targets results in more accurate prediction of cancer stage.

The sheer volume and size of histopathological images (e.g., 106MPixel) underscores the need for faster and more accurate Regions-of-interest (ROI) detection algorithms. In this paper, we propose such an algorithm, which has four main components that help achieve greater accuracy and faster speed: First, while using coarse-to-fine topology preserving segmentation as the baseline, the proposed algorithm uses a superpixel regularity optimization scheme for avoiding irregular and extremely small superpixels. Second, the proposed technique employs a prediction strategy to focus only on important superpixels at finer image levels. Third, the algorithm reuses the information gained from the coarsest image level at other finer image levels. Both the second and the third components drastically lower the complexity. Fourth, the algorithm employs a highly effective parallelization scheme using adaptive data partitioning, which gains high speedup. Experimental results, conducted on the BSD500 [1] and 500 whole-slide histological images from the National Lung Screening Trial (NLST)1dataset, confirm that the proposed algorithm gained 13 times speedup compared with the baseline, and around 160 times compared with SLIC [11], without losing accuracy.

Researchers are extensively investigating motion estimation for H.265 (HEVC), the newest video coding standard for wired and wireless environments. Reducing the complexity of encoding in mobile applications is essentially required for smooth transmission as well as storage. The principal contributor towards this complexity is the motion estimation component of the encoder. Parallel processing of motion estimation is an attractive option to cope with the high complexity but it poses a research challenge. This paper briefly describes some of the existing parallel and nearly parallel motion estimation algorithms. Next, we propose a parallel motion estimation scheme that employs different search patterns and various ranges of motion search. The target platform is a multicore parallel processing system. The experiments include the speedup, bit rate, and video quality, showing the efficiency of the proposed scheme. Different search patterns are compared as well.

This paper proposes a multi-objective evolutionary algorithm (MOEA)-based task scheduling approach for determining Pareto optimal solutions with simultaneous optimization of performance (P), energy (E), and temperature (T). Our algorithm includes problem-specific solution encoding, determining the initial population of the solution space, and the genetic operators that collectively work on generating efficient solutions in fast turnaround time. Multiple schedules offer a diverse range of values for makespan, energy consumed, and peak temperature and thus present an efficient way of identifying trade-offs among the desired objectives, for a given application and machine pair. We also present a methodology for selecting one solution from the Pareto front given the user's preference. The proposed algorithm for scheduling tasks to cores achieves three-way optimization with fast turnaround time. The proposed algorithm is advantageous because it reduces both energy and temperature together rather than in isolation. We evaluate the proposed algorithm using implementation and simulation, and compare it with integer linear programming as well as with other scheduling algorithms that are energy- or thermal-aware. The time complexity of the proposed scheme is considerably better than the compared algorithms.

With the continually growing popularity of online video sharing, energy consumption in video sharing servers has become an pivotal issue. Energy savings in video servers can be achieved by utilizing low power modes in disks, but this causes enhanced delay which is not desirable for video sharing services. In this paper, we present a new energy management scheme that jointly optimizes energy and delay for the video storage system. There are two salient characteristics of the proposed scheme. First, it exploits the unique workload characteristics of video sharing services. Second, it includes a new model that efficiently facilitates the selection of power modes for disks. Experiments show that our scheme achieves considerably more energy savings under the same delay level compared to the traditional threshold-based energy management scheme.

Enabled by high-speed networking in commercial, scientific, and government settings, the realm of high performance is burgeoning with greater amounts of computational and storage resources. Large-scale systems such as computational grids consume a significant amount of energy due to their massive sizes. The energy and cooling costs of such systems are often comparable to the procurement costs over a year period. In this survey, we will discuss allocation and scheduling algorithms, systems, and software for reducing power and energy dissipation of workflows on the target platforms of single processors, multicore processors, and distributed systems. Furthermore, recent research achievements will be investigated that deal with power and energy efficiency via different power management techniques and application scheduling algorithms. The article provides a comprehensive presentation of the architectural, software, and algorithmic issues for energy-aware scheduling of workflows on single, multicore, and parallel architectures. It also includes a systematic taxonomy of the algorithms developed in the literature based on the overall optimization goals and characteristics of applications.

This paper proposes an object-level rate control algorithm to jointly controlling the bit rates of multiple video objects. Utilizing noncooperative game theory, the proposed rate control algorithm mimics the behaviors of players representing video objects. Each player competes for available bits to optimize its visual quality. The algorithm finds an ¿optimal solution¿ in that it conforms to the mixed strategy Nash equilibrium, which is the probability distribution of the actions carried by the players that maximizes their expected payoffs (the number of bits). The game is played iteratively, and the expected payoff of each play is accumulated. The game terminates when all of the available bits for the specific time instant have been distributed to video object planes (VOPs). The advantage of the proposed scheme is that the bidding objects divide the bits among themselves automatically and fairly, according to their encoding complexity, and with an overall solution that is strategically optimal under the given circumstances. To minimize buffer fluctuation and avoid buffer overflow and underflow, a proportional-integral-derivative (PID) control based buffer policy is utilized.

Rate control in H.264/AVC aims to achieve the best tradeoff between encoding quality and bandwidth while satisfying the buffer restriction. Due to the improving efficiency of intra-only rate control, we propose an effective rate control scheme for intra-only encoding. The proposed scheme employs a novel rate-distortion (RD) model, a new complexity measure, a precise quantization parameter (QP) calculation method, and a simple but effective model adaptation mechanism for intra-frames. Experimental results demonstrate that, compared with JVT-W042, the proposed algorithm achieves higher precise bit estimation, provides more robust buffer control, and improves coding quality.

This paper presents a novel rate control algorithm for H.264/AVC video coding. Pertinent to the algorithm, the paper introduces a joint R-D model, a coding bit estimation approach, a picture complexity measurement, and a model update method. Specifically, the proposed picture complexity measurement employs a Harmonic Mean based approach to predict the coding complexity of a frame. These techniques collectively enhance the overall rate control performance. Experimental results demonstrate that the proposed algorithm outperforms JVT-W042 in providing robust buffer control, reducing frame skipping, and improving coding quality.

In mobile computing environments, a video encoder should be able to provide high quality of service, which is measured from two perspectives: first, the video quality at a given bit rate must be optimized; second, it should be able to efficiently utilize its power supply to prolong the battery operating time. In other words, it should be able to achieve low power consumption as well as lower video distortion. There is a pressing need to develop power efficient video coding techniques, which can also deliver high picture quality. We address several issues and research challenges, and potential solutions, including defining new power rate distortion model, encoder complexity, mapping power to coding parameters, optimization criteria, making and effective use of the battery power information, parameter analysis, and new optimization techniques.

This paper addresses the problem of how to efficiently manage the power consumption while preserving high visual quality performance in video coding for pervasive video applications. We define an optimization problem that corresponds to the minimization of both the power consumption and video distortion of a video encoder. A joint rate-complexity-distortion(R-C-D) model is developed to capture and control the general R-C-D behavior of video coding. Based on the analysis of the proposed model, optimization strategies are developed to achieve good video quality while maximizing the battery service life. We demonstrate how the observations and optimization strategies can be utilized in a practical parameterized encoder under various preferences of quality and power. We perform simulations on an instruction set simulator to exhibit the effectiveness of the proposed scheme.

This paper proposes a non-cooperative game based technique to replicate data objects across a distributed system of multiple servers in order to reduce user perceived Web access delays. In the proposed technique computational agents represent servers and compete with each other to optimize the performance of their servers. The optimality of a non-cooperative game is typically described by Nash equilibrium, which is based on spontaneous and non-deterministic strategies. However, Nash equilibrium may or may not guarantee system-wide performance. Furthermore, there can be multiple Nash equilibria, making it difficult to decide which one is the best. In contrast, the proposed technique uses the notion of pure Nash equilibrium, which if achieved, guarantees stable optimal performance. In the proposed technique, agents use deterministic strategies that work in conjunction with their self-interested nature but ensure system-wide performance enhancement. In general, the existence of a pure Nash equilibrium is hard to achieve, but we prove the existence of such equilibrium in the proposed technique. The proposed technique is also experimentally compared against some well-known conventional replica allocation methods, such as branch and bound, greedy, and genetic algorithms.

With the explosive growth in computers and the growing scarcity in electric supply, reduction of energy consumption in large-scale computing systems has become a research issue of paramount importance. In this paper, we study the problem of allocation of tasks onto a computational grid, with the aim to simultaneously minimize the energy consumption and the makespan subject to the constraints of deadlines and tasks' architectural requirements. We propose a solution from cooperative game theory based on the concept of Nash bargaining solution. In this cooperative game, machines collectively arrive at a decision that describes the task allocation that is collectively best for the system, ensuring that the allocations are both energy and makespan optimized. Through rigorous mathematical proofs we show that the proposed cooperative game in mere O(n mlog(m)) time (where n is the number of tasks and m is the number of machines in the system) produces a Nash bargaining solution that guarantees Pareto-optimally. The simulation results show that the proposed technique achieves superior performance compared to the greedy and linear relaxation (LR) heuristics, and with competitive performance relative to the optimal solution implemented in LINDO for small-scale problems.

Multi-core processors are beginning to revolutionize the landscape of high-performance computing. In this paper, we address the problem of power-aware scheduling/mapping of tasks onto heterogeneous and homogeneous multi-core processor architectures. The objective of scheduling is to minimize the energy consumption as well as the makespan of computationally intensive problems. The multi-objective optimization problem is not properly handled by conventional approaches that try to maximize a single objective. Our proposed solution is based on game theory. We formulate the problem as a cooperate game. Although we can guarantee the existence of a Bargaining Point in this problem, the classical cooperative game theoretical techniques such as the Nash axiomatic technique cannot be used to identify the Bargaining Point due to low convergence rates and high complexity. Hence, we transform the problem to a max-max-min problem such that it can generate solutions with fast turnaround time.

Adaptive replication of data items on servers of a mobile ad hoc network can alleviate access delays. The selection of data items and servers requires solving a constrained optimization problem, that is in general NP-complete. The problem is further complicated by frequent partitions of the ad hoc network. In this paper, a mathematical model for data replication in ad hoc networks is formulated. We treat the mobile servers in the ad hoc network as self-interested entities, hence they have the capability to manipulate the outcome of a resource allocation mechanism by misrepresenting their valuations. We design a game theoretic "truthful" mechanism in which replicas are allocated to mobile servers based on reported valuations. We sketch the exact properties of the truthful mechanism and derive a payment scheme that suppresses the selfish behavior of the mobile servers. The proposed technique is extensively evaluated against three ad hoc network replica allocation methods: (a) extended static access frequency, (b) extended dynamic access frequency and neighborhood, and (c) extended dynamic connectivity grouping. The experimental results reveal that the proposed approach outperforms the three techniques in solution quality and has competitive execution times.

The 14 regular papers and two brief papers in this special issue capture some of the state-of-the-art research on video surveillance issues, provide comprehensive overview of existing techniques, and propose novel solutions for important research problems.

Motion estimation is a multistep process that encompasses techniques such as motion vector prediction, determination of search range and search patterns, and identification of termination criteria. Each of these techniques has several diversions that may suit a particular set of video characteristics. It would be hard to conceive a universal algorithm that can perform well for all kinds of video contents. However, if important characteristics of a video sequence can be identified and utilized for adjusting various steps of motion estimation, one can design an adjustable algorithm that can tune its parameters to suit the video at hand. A multistage motion estimation algorithm that includes a pre-stage for analyzing the motion characteristics of a video sequence online is proposed. This stage predicts the motion vector field (MVF) from the previous coded frame, and clusters macroblocks into background and foreground regions based on the predicted MVF. The information from the pre-stage are passed on to the next stage, which includes a mathematical model for block distortion surface to estimate the distance from the current search point to the global optimal position. This allows the motion estimation stage to adjust its search strategies accordingly. The search is performed on a precise area according to the statistical properties of the motion vector prediction error, separately for foreground and background regions. The proposed algorithm, including the pre-stage, is fast and, therefore, is suitable for online and real-time encoding. Extensive simulation results obtained for several video sequences affirm the effectiveness of the proposed algorithm. The self-tuning property enables the algorithm to perform well for several types of benchmark sequences, yielding better video quality without exceeding the time complexity as compared to the other predictive motion estimation algorithms.

Creating replicas of frequently accessed data objects across a read intensive network can lead to reduced communication cost and end-user response time. On the contrary, data replication in the presence of writes incurs extra cost due to multiple updates. The selection of data objects and servers requires solving a constraint optimization problem, which is NP-complete in general. A majority of the current state-of-the-art replica placement techniques suffer from high computational complexity issues. To circumvent such issues, we propose a cooperative game theoretical technique in which the servers (players) in the system collectively deliberate to converge at a replica schema that is beneficial to the system as a whole. In particular we make use of the Aumann-Shapley mechanism of cooperative game theory to propose an effective replica placement technique that yields good solutions when the system is very heavily loaded. Experimental comparisons are made against: (1) branch and bound, (2) greedy, (3) genetic, (4) Dutch auction, and (5) English auction. As demonstrated by the experimental results, the proposed technique maintains superior solution quality in terms of lower communication cost and reduced execution time.

Replicating data objects onto servers across a system can alleviate access delays. The selection of data objects and servers requires solving a constraint optimization problem, which is NP-complete in general. A majority of conventional replica placement techniques falter on issues of scalability or solution quality. To counteract such issues, we propose a game theoretical replica placement technique, in which computational agents compete for the allocation or reallocation of replicas onto their servers in order to reduce the user perceived access delays. The technique is based upon six well-defined axioms, each guaranteeing certain basic game theoretical properties. This eccentric method of designing game theoretical techniques using axioms is unique in the literature and takes away from the designers the cumbersome mathematical details of game theory. The distinctive feature of these axioms is that when amassed together, their individual properties constrict into one system-wide performance enhancement property, which in our case is the reduction of access time. The control of the proposed technique is "semi-distributed" in nature, wherein all the heavy processing is done on the servers of the distributed system and the central body is only required to take a binary decision: (0) not to replicate or (1) to replicate. This semi-distributed approach makes the technique scalable and helps solutions to converge in a fast turn-around time without loosing much of the solution quality. Experimental comparisons are made against: 1) branch and bound, 2) greedy, 3) genetic, 4) Dutch auction, and 5) English auction. As attested by the results, the proposed technique maintains superior solution quality in terms of lower communication cost and reduced execution time.

With the rapid growth of servers and applications spurred by the Internet, the power consumption of servers has become critically important and must be efficiently managed. High energy consumption also translates into excessive heat dissipation which in turn, increases cooling costs and causes servers to become more prone to failure. This paper presents a theoretical and experimental framework and general methodology for hierarchical autonomic power & performance management in high performance distributed data centers. We optimize for power & performance (performance/watt) at each level of the hierarchy while maintaining scalability. We adopt mathematically-rigorous optimization approach to provide the application with the required amount of memory at runtime. This enables us to transition the unused memory capacity to a low power state. Our experimental results show a maximum performance/watt improvement of 88.48% compared to traditional techniques. We also present preliminary results of using game theory to optimize performance/watt at the cluster level of a data center. Our cooperative technique reduces the power consumption by 65% when compared to traditional techniques (min-min heuristic).

Object-based video coding, such as MPEG-4, supports the encoding and manipulating of individual video object. Rate control algorithm for multiple video object coding shall adapt to the perceptual importance of the video object. For this purpose, we present a joint rate control algorithm for coding multiple video objects. The proposed algorithm is aiming to obtain superior quality for the video objects with higher perceptual importance, while squeezing bits from the video objects with lower perceptual importance. The quality gaps between video objects is regulated to the target level through the proportional-derivative feedback design.

In this paper, we consider the problem of MPEG-4 visual simple profile to H.264/AVC baseline profile (BP) transcoding. An efficient transcoding algorithm with fast mode selection and motion vector refinement is proposed. The proposed algorithm exploits the side information from the decoding stage to predict the coding modes and MVs of H.264/AVC BP coding. The proposed algorithm consists of two parts: INTRA macroblocks (MBs) transcoding and INTER MBs transcoding. By reusing the side information during the decoding stage, these techniques provide significant complexity reduction, when compared with the fully spatial domain approach.

Object based coding can potentially achieve a higher degree of compression and better visual quality. This paper proposes a multiple object rate control algorithm for video transmissions over wireless systems. The algorithm adopts an efficient bit allocation strategy to intelligently allocates more bits to important objects, while adapts to time-varying wireless channels. Simulation results for both wireless downlink and uplink channels demonstrate that the proposed algorithm effectively improves perceptual quality on important objects, significantly reduces VOP (Video Object Plane in MPEG-4) skipping and thereby, maintains the motion continuity in wireless video transmissions.

This paper addresses the issues of how to efficiently manage the power consumption while preserving high quality performance for video coding in futuristic pervasive computing environments. We formulate an optimization problem that corresponds to minimize both the power consumption and video distortion. A joint rate-complexity-distortion (R-C-D) model is developed to describe and control the general R-C-D behavior of video coding. The model facilitates to develop effective schemes based on the analysis of the optimization problem in order to achieve good video quality while maximizing the battery service life. We perform simulations on an instruction set simulator to demonstrate the effectiveness of the proposed schemes.

Exploitation of redundancies for superior coding efficiency is one of the major research issues in multi-view video coding (MVC). However, this incurs extra computation, counteracting the benefit gained from coding efficiency. This paper exploits inter-view correlations among video objects and background to lower the prediction complexity while achieving high coding efficiency in MVC. We propose an effective object-based scheme that utilizes video object information obtained from the coded base view. This information assists to predict disparity vectors and motion vectors in enhancement views (EVs) by employing object registration and warping. This leads to high compression and low-complexity coding scheme for EVs. The proposed scheme provides higher coding efficiency when compared to the segmentation-free scheme, while achieving lower computational complexity.

In this paper we consider, compare and analyze three game theoretical grid resource allocation mechanisms. Namely, 1) the non-cooperative sealed-bid method where tasks are auctioned off to the highest bidder, 2) the semi-cooperative n-round sealed-bid method in which each site delegate its work to others if it cannot perform the work itself, and 3) the cooperative method in which all of the sites deliberate with one another to execute all the tasks as efficiently as possible. To experimentally evaluate the above mentioned techniques, we perform extensive simulation studies that effectively encapsulate the task and machine heterogeneity. The tasks are assumed to be independent and bear multiple execution time deadlines. The simulation model is built around a hierarchical grid infrastructure where machines are abstracted into larger computing centers labeled "federations", each of which are responsible for managing their own resources independently. These federations are then linked together with a primary portal to which grid tasks would be submitted. To measure the effectiveness of these game theoretical techniques, the recorded performance is evaluated against a conventional baseline method in which tasks are randomly assigned to the sites without any task execution guarantee.

Minimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the “best” mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations.

This paper presents a game theory based technique for optimizing the bit rate control in video coding. Game theory, by virtue of its enormous potential for solving constrained optimization problems, has been effectively utilized in several branches of natural and social sciences. But this paper is the first attempt in using game theory for video compression. The objective is to optimize the perceptual quality while guaranteeing "fairness" in bit allocation among macroblocks (MBs). The proposed technique is a dual-level rate control algorithm: At the first level, the algorithm allocates the target bits to frames based on their coding complexity; a method to estimate the coding complexity of the remaining frames is proposed. At the second level, MBs of a frame play cooperative games such that each MB competes for a fair share of resources (bits) to optimize its quantization scale while considering the human visual system (HVS) perceptual property. We formulate the rate control problem by defining players, strategies and objective function. Since the whole frame is an entity perceived by viewers, MBs compete cooperatively under a global objective of achieving the best quality with the given bit constraint. The major advantage of the proposed approach is that the cooperative game leads to an optimal and fair bit allocation strategy based on the Nash bargaining solution. Another advantage is that it allows multi-objective optimization with multiple decision makers (e.g., MBs) in order to achieve accurate bit rate with good perceptual quality while maintaining a stable buffer level. Several extensions of the work are possible.

Motion estimation (ME) is a multistep process that involves not one, but a combination of techniques, such as motion starting point, motion search patterns, and adaptive control to curb the search, avoidance of search stationary regions, etc. The collective efficiency of these techniques is what makes a ME algorithm robust and efficient across the board. This paper proposes a ME algorithm that is an embodiment of several effective ideas for finding the most accurate motion vectors (MVs) with the aim to maximize the encoding speed as well as the visual quality. The proposed algorithm takes advantage of the correlation between MVs in both spatial and temporal domains, controls to curb the search, avoids of search stationary regions, and uses switchable shape search patterns to accelerate motion search. The algorithm yields very similar quality compared to the full search but with several hundred times faster speed. We have evaluated the algorithm through a comprehensive performance study that shows that the proposed algorithm achieves substantial speedup without quality loss for a wide range of video sequences, compared with the ME techniques recommended by the MPEG-4 committee.

In this paper, we propose a joint source-channel region-based rate control algorithm for real-time video transmissions over wireless systems. During the video transmission, the channel throughput available to the video encoder in the wireless systems is inherently variable, due to the retransmission of the error packets using the automatic repeat request (ARQ) error control. The variable data rate of the wireless system is characterized by the packet-level Gilbert two-state Markov Model, the parameters of which are extracted from the statistical properties of the channel information obtained from the wireless channel simulator. The proposed algorithm adopts a fast but effective block-based segmentation method to extract the regions of interest. Unlike traditional bit allocation methods used in the region/content-based rate control, the algorithm exploits the most effective criteria "coding qualities" as quantitative factors to directly control bit allocation among different regions so as to achieve better visual quality in the regions of interest. The computational complexity of the algorithm is low making it suitable for real-time applications. Compared with the MPEG-4 rate control algorithm, our algorithm can effectively enhance the perceptual quality for the regions of interest and significantly reduce the number of frame skipping; thereby, improve the smoothness of the video.

The Internet now offers more than just simple information to the users. Decision makers can now issue analytical, as opposed to transactional, queries that involve massive data (such as, aggregations of millions of rows in a relational database) in order to identify useful trends and patterns. Such queries are often referred to as Online-analytical processing (OLAP). Typically, pages carrying query results do not exhibit temporal locality and, therefore, are not considered for caching at Internet proxies. In OLAP processing, this is a major problem as the cost of these queries is significantly larger than that of the transactional queries. This paper proposes a technique to reduce the response time for OLAP queries originating from geographically distributed private LANs and issued through the Web toward a central data warehouse (DW) of an enterprise. An active caching scheme is introduced that enables the LAN proxies to cache some parts of the data, together with the semantics of the DW, in order to process queries and construct the resulting pages. OLAP queries arriving at the proxy are either satisfied locally or from the DW, depending on the relative access costs. We formulate a cost model for characterizing the respective latencies, taking into consideration the combined effects of both common Web access and query processing. We propose a cache admittance and replacement algorithm that operates on a hybrid Web-OLAP input, outperforming both pure-Web and pure-OLAP caching schemes

The Replica Placement Problem (RPP) aims at creating a set of duplicated data objects across the nodes of a distributed system in order to optimize certain criteria. Typically, RPP formulations fall into two categories: static and dynamic. The first assumes that access statistics are estimated in advance and remain static, and, therefore, a one-time replica distribution is sufficient (IRPP). In contrast, dynamic methods change the replicas in the network potentially upon every request. This paper proposes an alternative technique, named Continuous Replica Placement Problem (CRPP), which falls between the two extreme approaches. CRPP can be defined as: Given an already implemented replication scheme and estimated access statistics for the next time period, define a new replication scheme, subject to optimization criteria and constraints. As we show in the problem formulation, CRPP is different in that the existing heuristics in the literature cannot be used either statically or dynamically to solve the problem. In fact, even with the most careful design, their performance will be inferior since CRPP embeds a scheduling problem to facilitate the proposed mechanism. We provide insight on the intricacies of CRPP and propose various heuristics.

Mobile devices performing video coding and streaming over wireless and pervasive communication networks are limited in energy supply. To prolong the operational lifetime of these devices, an embedded video encoding system should be able to adjust its computational complexity and energy consumption as demanded by the situation and its environment. To analyze, control, and optimize the rate-distortion (R-D) behavior of the wireless video communication system under the energy constraint, we develop a power-rate-distortion (P-R-D) analysis framework, which extends the traditional R-D analysis by including another dimension, the power consumption. Specifically, in this paper, we analyze the encoding mechanism of typical video coding systems, and develop a parametric video encoding architecture which is fully scalable in computational complexity. Using dynamic voltage scaling (DVS), an energy consumption management technology recently developed in CMOS circuits design, the complexity scalability can be translated into the energy consumption scalability of the video encoder. We investigate the R-D behavior of the complexity control parameters and establish an analytic P-R-D model. Both theoretically and experimentally, we show that, using this P-R-D model, the video coding system is able to automatically adjust its complexity control parameters to match the available energy supply of the mobile device while maximizing the picture quality. The P-R-D model provides a theoretical guideline for system design and performance optimization in mobile video communication under energy constraints.

The embedded multireference frames selection with variable block-size motion compensation model drastically increases the computational complexity of the H.264/AVC video coding standard. This paper proposes an adaptive hierarchical motion estimation (ME) algorithm for H.264/AVC with the objective of minimizing the complexity while maximizing the visual quality. The proposed algorithm is based on a framework that exploits the "history" of the motion intensity from a video sequence in order to control ME. The complexity and memory requirement for this meta information is low. The algorithm determines the motion intensity of a video sequence at three levels and accordingly employs different ME techniques. The results certify that the history-based hierarchical information can be very effective in improving the efficiency of ME.

Object-based coding can potentially achieve a higher degree of compression and better visual quality. The objects in a scene are not always synchronous, that is, they have different temporal resolutions. In some applications, it is more efficient to transmit asynchronous objects with different temporal rates so as to achieve a better tradeoff between temporal and spatial resolutions. This requires to balance the qualities of individual objects while ensuring an overall visual quality with a given bit rate. This paper proposes a rate control algorithm for multiple video object encoding, which is suitable for both synchronous and asynchronous transmissions. The algorithm aims to maximize scene quality with an accurate bit rate, while efficiently handling buffer fullness. Using an efficient bit allocation strategy, the algorithm achieves accurate target bit rates, provides good coding quality, and decreases buffer overflow/underflow. The proposed algorithm also allows flexible priority adjustment among multiple objects to ensure overall better visual perception. Designed primarily for asynchronous objects, the algorithm treats the synchronous objects as a special case. Experimental results demonstrate that, when giving suitable asynchronous video object planes rates, the proposed algorithm achieves good temporal-spatial tradeoff while yielding accurate rate regulation and effective buffer control.

One of the fundamental challenges in deploying multimedia systems, such as telemedicine, education, space endeavors, marketing, crisis management, transportation, and military, is to deliver smooth and uninterruptible flow of audio-visual information, anytime and anywhere. A multimedia system may consist of various devices (PCs, laptops, PDAs, smart phones, etc.) interconnected via heterogeneous wireline and wireless networks. In such systems, multimedia content originally authored and compressed with a certain format may need bit rate adjustment and format conversion in order to allow access by receiving devices with diverse capabilities (display, memory, processing, decoder). Thus, a transcoding mechanism is required to make the content adaptive to the capabilities of diverse networks and client devices. A video transcoder can perform several additional functions. For example, if the bandwidth required for a particular video is fluctuating due to congestion or other causes, a transcoder can provide fine and dynamic adjustments in the bit rate of the video bitstream in the compressed domain without imposing additional functional requirements in the decoder. In addition, a video transcoder can change the coding parameters of the compressed video, adjust spatial and temporal resolution, and modify the video content and/or the coding standard used. This paper provides an overview of several video transcoding techniques and some of the related research issues. We introduce some of the basic concepts of video transcoding, and then review and contrast various approaches while highlighting critical research issues. We propose solutions to some of these research issues, and identify possible research directions.

This paper proposes a joint source-channel rate control algorithm for real-time video transmissions over WCDMA systems. The algorithm encompasses a region-based bit allocation strategy and a macro block-based segmentation technique. To enhance the video quality while saving bits, the algorithm effectively allocates more bits to important parts of a video frame, and also adapts to time-varying WCDMA channels. Simulation results demonstrate that the proposed algorithm effectively improves perceptual quality, reduces frame skipping and, thereby, maintains the motion continuity in wireless video transmissions.

The embedded motion compensation model of the new H.264/AVC video coding standard dramatically increases the computational complexity of motion estimation. We propose a fast motion estimation algorithm using a hierarchical motion intensity structure to lower the computational complexity of the motion estimation in H.264/AVC. The proposed algorithm is mainly based on a multi-level motion intensity structure. It determines the motion intensity at three levels and, accordingly, uses different motion estimation techniques to find a more accurate, and faster, motion vector (MV). Experimental results show that the proposed algorithm provides promising performance in terms of the computational speedup and video reconstruction quality.

This paper proposes a median-bias fast priority search algorithm for motion estimation. The main characteristic of the proposed algorithm is that it adapts a priority median-bias search pattern enabling the identification of locations with higher probability of finding the motion vector. Moreover, based on the history of motion vectors, the algorithm includes a robust region detection technique to avoid unnecessary searches in the static background region. A minimum-distortion based analytical threshold is proposed to stop the search quickly when a "good enough" motion vector is achieved. Experimental results show that by using the proposed algorithm, the speed and accuracy of motion estimation are improved compared with the conventional approaches.

A multistage motion estimation scheme is proposed. The scheme extracts video characteristics by first performing an online video analysis separately for foreground and background regions. Motion parameters are extracted and passed to the next stage. The next stage includes a mathematical model for the block distortion surface (BDS) that enables the algorithm to accordingly adjust its search technique. The search is performed on a precise search area adaptive to the statistical property of the motion vector prediction error. Due to its self-tuning property, not only does the proposed scheme adapt to scenes by yielding better visual quality but it also yields a lower computational complexity, compared with the other predictive motion estimation algorithms on standard benchmark sequences.

This work deals with layered video transmission over wireless networks. We focus on deriving the required bandwidth provisioning for each layered video given their respective QoS target. We model the layered video traffic by a discrete time batch Markovian arrival process (DBMAP) with marked transitions. We assume the link level behavior of the wireless channel can be modeled by a hidden Markov model (HMM), and the network supports automatic repeat request (ARQ) operation. We show that the video data transmission buffer can be modeled as a G/D/c queue with time dependent feedback, and propose to approximate the ARQ feedback traffic by an HMM modulated DBMAP process. Based on the effective bandwidth approach, we derive the required channel capacity for both the input video traffic and the ARQ feedback traffic in order to meet the given QoS targets.

In video coding and streaming over wireless communication network, the power-demanding video encoding operates on the mobile devices with limited energy supply. To analyze, control, and optimize the rate-distortion (R-D) behavior of the wireless video communication system under the energy constraint, we need to develop a power-rate-distortion (P-R-D) analysis framework, which extends the traditional R-D analysis by including another dimension, the power consumption. Specifically, in this paper, we analyze the encoding mechanism of typical video encoding systems and develop a parametric video encoding architecture which is fully scalable in computational complexity. Using dynamic voltage scaling (DVS), a hardware technology recently developed in CMOS circuits design, the complexity scalability can be translated into the power consumption scalability of the video encoder. We investigate the rate-distortion behaviors of the complexity control parameters and establish an analytic framework to explore the P-R-D behavior of the video encoding system. Both theoretically and experimentally, we show that, using this P-R-D model, the encoding system is able to automatically adjust its complexity control parameters to match the available energy supply of the mobile device while maximizing the picture quality. The P-R-D model provides a theoretical guideline for system design and performance optimization in wireless video communication under energy constraint, especially over the wireless video sensor network.

This paper proposes a rate control algorithm for single and multiple objects video coding. The algorithm exploits prediction and feedback control to achieve accurate bit rate while maximizing the picture quality and simultaneously effectively handling buffer fullness. The algorithm estimates the bit budget of a frame based on its global coding complexity, and dynamically distributes the target bits for each object within a frame according to the object's coding complexity. Exploiting a novel buffer controller based on the proportional-integral-derivative (PID) technique used in automatic control systems, the algorithm effectively reduces the deviation between the current buffer fullness and the target buffer fullness, and minimizes the buffer overflow or underflow. The algorithm dynamically adjusts several parameters to further improve the system performance. A scene-change handling method is used to deal with scene changes. The combination of prediction and feedback control improves the adaptability of the rate controller under complicated environments; it also decreases the effect of random disturbance and the deviation caused by the variance between the real system and its statistical model. Overall, the proposed algorithm successfully achieves accurate target bit rate, provides promising coding quality, decreases buffer overflow/underflow and lowers the impact of a scene change.

Notoriously high delays in accessing Web pages loaded with massive multimedia objects are highly undesirable. Inspired by the requirements of news agencies and other information providers to include multimedia content in their pages, this paper proposes a new solution to the problem of minimizing the Web response time. We consider an environment that consists of a central multimedia repository and various sites physically dispersed. Our approach is based on simultaneous downloading of some of the embedded multimedia objects from the repository, and the rest from the regional servers. We propose a cost model to formalize the relative benefits of the proposed scheme, and design an algorithm that replicates multimedia objects so as to take advantage of concurrency in data transferring. An extensive simulation study evaluates the performance of the proposed replication policy under storage and processing capacity constraints, as well as with various network transfer rates. Comparisons are carried out with alternative schemes.

Video scenes containing multiple objects can potentially achieve higher degree of compression and better visual quality with individual coding for each object. Video objects are not always synchronous, implying each object may have a separate temporal resolution. This paper proposes a rate control algorithm for multiple video object encoding. Using a novel bit allocation strategy, the algorithm achieves accurate target bit rate, provides good visual quality, and decreases buffer overflow/underflow. Experimental results for both synchronous and asynchronous multiple video object encoding demonstrate that, when compared with the existing rate control scheme recommended by the MPEG-4 standard, the proposed algorithm provide better temporal-spatial tradeoff with more accurate rate regulation.

In this paper we propose a traffic model for delivering scalable video encoded with multiple layers on heterogeneous networks. The model is based on Markovian arrival process with marked transitions. The state of the underlying Markov chain of the video arrival process is derived from the correlation feature found in the video data. The base layer and enhancement layer video frame size pairs are decided by a cluster detection algorithm; each cluster corresponds to one state of the Markov chain. The joint base and enhancement layer video frame size distribution for each state of the Markov chain is approximated by multivariate normal distribution. Simulation study on the traffic model data and the video trace data is carried out and compared with the model. The results show that the proposed traffic model can predict the network performance with good accuracy.

Configuration similarity is a special form of content-based image retrieval that considers relative object locations. It can be used as a standalone method, or to complement retrieval based on visual or semantic features. The corresponding queries ask for sets of objects that satisfy some spatio-temporal constraints, e.g., "find all triplets of objects (v/sub 1/, v/sub 2/, v/sub 3/), such that v/sub 1/ is northeast of v/sub 2/, which is inside v/sub 3/." Exhaustive processing (i.e., retrieval of the best solutions) of configuration similarity queries, in general, has exponential complexity and fast search for sub-optimal solutions is the only way to deal with the vast amounts of multimedia information in several real-time applications. In this paper we first discuss the utilization of nonsystematic search heuristics, based on genetic algorithms, simulated annealing and hill climbing approaches. An extensive experimentation with real and synthetic datasets reveals that hill climbing techniques are the best for the current problem; therefore, as a subsequent step we study the search space, and develop improved variations of hill climbing that take advantage of the special structure of the problem to enhance speed. The proposed heuristic methods significantly outperform systematic search when there is only limited time for query processing.

Video coding is a complex process, comprising a combination of spatial, temporal and statistical data reduction techniques. Of these techniques, motion estimation taking advantage of inter-frame information redundancy, plays the most vital role. The overwhelming complexity of motion estimation using a brute-force search has prompted researchers to propose a myriad of algorithms, yet finding the "most efficient" algorithm remains an open research problem. Recently, the MPEG-4 committee, after a rigorous evaluation, have recommended a motion estimation algorithm that performs very well in terms of speed and picture quality. We propose a motion estimation algorithm that is a combination of a number of novel ideas for finding more accurate motion vectors and with a faster speed. The proposed algorithm, named as adaptive motion search with elastic diamond (AMSED) algorithm, takes advantages of the correlation between motion vectors in both spatial and temporal domains, and uses special diamond shaped search patterns to accelerate motion search. The new algorithm achieves very close quality compared to the full search, but with several hundred times speedup. In term of speed, compared with the motion estimation technique recommended by the MPEG-4 committee, MVFAST (motion vector field adaptive fast search technique), AMSED can achieve more than 200% speedup.

MPEG-2 MP@ML has been used widely in consumer electronics, and 422Profile is a special conformance point for the studio and post-production environment. In this paper, a high performance MPEG-2 Profile transcoding based on MC-DCT is proposed, which can dramatically reduce the computation and hardware complexity. The simulation result verified that the proposed approach can get higher quality in luminance component at the cost of slight quality deterioration in chroma space compared with the pixel domain method. It is much effective to be used in the real-time environments.

The Internet is offering more than just regular Web pages to the users. Decision makers can now issue analytical, as opposed to transactional, queries that involve massive data (such as, aggregations of millions of rows in a relational database) in order to identify useful trends and patterns. Such queries are referred to as On-Line-Analytical-Processing (OLAP) queries. Typically, pages carrying query results do not exhibit temporal locality and, therefore, are not considered for caching at WWW proxies. In OLAP processing, this becomes a major hurdle as the cost of such queries is much higher than traditional transactional queries. This paper proposes a systematic technique to reduce the response time for OLAP queries originating from geographically distributed private LANs and issued through the Web towards the central data warehouse (DW) of an enterprise. An active caching scheme is proposed that enables the LAN proxies to cache some parts of the data, together with the semantics of the DW in order to process queries and construct the resulting pages. OLAP queries arriving at the proxy are either satisfied locally or from the DW, depending on the relative access costs. We formulate a cost model for characterizing the latencies of these queries, taking into consideration normal Web access as well as analytical processing. We propose a cache admittance and replacement algorithm that outperforms a widely accepted caching algorithm.

We present the optimization and performance evaluation of a software-based H.263 video encoder. The objective is to maximize the encoding rate without losing the picture quality on an ordinary single processor computer such as a PC or a workstation. This requires optimization at all design and implementation phases, including algorithmic enhancements, efficient implementations of all encoding modules, and taking advantage of certain architectural features of the machine. We design efficient algorithms for DCT and fast motion estimation, and exploit various techniques to speed up the processing, including a number of compiler optimizations and removal of redundant operations. For exploiting the architectural features of the machine, we make use of low-level machine primitives such as Sun UltraSPARC's visual instruction set and Intel's multimedia extension, which accelerate the computation in a single instruction stream multiple data stream fashion. Extensive benchmarking is carried out on three platforms: a 167-MHz Sun UltraSPARC-1 workstation, a 233-MHz Pentium II PC, and a 600-MHz Pentium III PC. We examine the effect of each type of optimization for every coding mode of H.263, highlighting the tradeoffs between quality and complexity. The results also allow us to make an interesting comparison between the workstation and the PCs. The encoder yields 45.68 frames per second (frames/s) on the Pentium III PC, 18.13 frames/s on the Pentium II PC, and 12.17 frames/s on the workstation for QCIF resolution video with high perceptual quality at reasonable bit rates, which are sufficient for most of the general switched telephone networks based video telephony applications. The paper concludes by suggesting optimum coding options.

Creating replicas of frequently accessed objects across a read-intensive network can result in large bandwidth savings which, in turn, can lead to reduction in user response time. On the contrary, data replication in the presence of writes incurs extra cost due to multiple updates. The set of sites at which an object is replicated constitutes its replication scheme. Finding an optimal replication scheme that minimizes the amount of network traffic given read and write frequencies for various objects, is NP-complete in general. We propose two heuristics to deal with this problem for static read and write patterns. The first is a simple and fast greedy heuristic that yields good solutions when the system is predominantly read-oriented. The second is a genetic algorithm that through an efficient exploration of the solution space provides better solutions for cases where the greedy heuristic does not perform well. We also propose an extended genetic algorithm that rapidly adapts to the dynamically changing characteristics such as the frequency of reads and writes for particular objects.

Dynamic replication algorithms aim at allocating, migrating and deleting copies of an object over various Internet hosts, according to the access patterns exhibited online, so as to improve object proximity for the end-users and/or load-balance the servers. Most of the existing algorithms try to disseminate the objects of an entire Internet Service Provider (ISP), without taking into account the needs and characteristics of specific web sites with large commercial value. In this paper we tackle the replication problem in an Internet environment, inspired by the need of news agencies and other information providers to include in their pages multimedia content without incurring high access delays. We consider an environment that consists of a central multimedia repository and various physically dispersed sires. We propose a cost model to formalize the replication of multimedia objects located at the repository which can result in decreasing the download time. Taking into account implementation issues, such as the storage and processing capacity constraints, the proposed replication policy is evaluated and compared with alternatives including an ideal LRU caching scheme. Qualitative comparisons with the other replication schemes are reported as well.

Motion estimation (ME) is an important part of the MPEG-4 encoder, due to its significant impact on the bitrate and the output quality of the encoded sequence. Unfortunately this feature occupies a significant part of the encoding time especially when using the straightforward full search (FS) algorithm. The diamond search (DS) was recently accepted as a fast motion estimation algorithm for the MPEG-4 VM. In this paper we propose a new algorithm named advanced diamond zonal search (ADZS), which is significantly faster than DS (in terms of number of checking points and total encoding time) and gives similar, if not better, quality (in terms of PSNR) of the output sequence. This is more obvious in the high bit rate cases. Our experiments verify the superiority of the proposed algorithm.

In this paper, we consider the problem of scheduling and mapping precedence-constrained tasks to a network of heterogeneous processors. In such systems, processors are usually physically distributed, implying that the communication cost is considerably higher than in tightly coupled multiprocessors. Therefore, scheduling and mapping algorithms for such systems must schedule the tasks as well as the communication traffic by treating both the processors and communication links as important resources. We propose an algorithm that achieves these objectives and adapts its tasks scheduling and mapping decisions according to the given network topology. Just like tasks, messages are also scheduled and mapped to suitable links during the minimization of the finish times of tasks. Heterogeneity of processors is exploited by scheduling critical tasks to the fastest processors. Our extensive experimental study has demonstrated that the proposed algorithm is efficient, robust, and yields consistent performance over a wide range of scheduling parameters.

The fast growth of multimedia information in image and video databases has triggered research on efficient retrieval methods.This paper deals with structural queries, a type of content-based retrieval where similarity is not defined on visual properties such as color and texture, but on object relations in space.We propose the application of heuristic algorithms which provide good, but not necessarily optimal, solutions in a pre-determined time period, and compare our approach with systematic search methods which are guaranteed to find optimal solutions but require exponential time in the worst case.The quality of the output is calculated using a relation framework which is an extension of Allen's relations.With this framework our methods can be applied in multiple resolutions and dimensions, thus covering a wide range of applications in spatial, multimedia and video systems.

Distributed information processing, in many WWW applications, requires access to and the transfer and synchronization of large multimedia data objects (MDOs) across the communication network. Moreover, end users expect very fast response times and high QoS. Since the transfer of large MDOs across the communication network contributes to the response time observed by the end users, the problem of allocating these MDOs so as to minimize the response time is challenging. This problem becomes more complex in the context of hypermedia documents, in which the MDOs need to be synchronized during presentation to the end users. The basic problem of data allocation in distributed database environments is NP-complete. Therefore, there is a need to pursue and evaluate solutions based on heuristics which generate near-optimal MDO allocation. We address this problem by: (1) conceptualizing this problem by using a navigational model to represent hypermedia documents and their access behavior by end users, and by capturing the synchronization requirements on MDOs, (2) formulating the problem by developing a base case cost model for response time and generalizing it to incorporate user interaction and buffer memory constraints, (3) designing two algorithms to find near-optimal solutions for allocating MDOs of the hypermedia documents while adhering to the synchronization requirements, and (4) evaluating the trade-off between the time complexity to obtain the solution and the solution quality by comparing the solutions generated by the algorithms with the optimal solutions generated through an exhaustive search.

MPEG-4 currently being finalized by the Moving Pictures Experts Group of the ISO is a multimedia standard, MPEG-4 aims to support content-based coding of audio, text, image, and video (synthetic and natural) data, multiplexing of coded data, as well as composition and representation of audiovisual scenes. One of the most critical components of an MPEG-4 environment is the system encoder. An MPEG-4 scene may contain several audio and video objects, images, and text, each of which must be encoded individually and then multiplexed to form the system bitstream. Due to its flexible features, object-based nature, and provision for user interaction, MPEG-4 encoder is highly suitable for a software-based implementation. A full-scale software-based MPEG-J system encoder with real-time encoding speed is a nontrivial task and requires massive computation. We have built such an encoder using a cluster of workstations collectively working as a virtual parallel machine. Parallel processing of MPEG-4 encoder needs to be carried out carefully as objects may appear or disappear dynamically in a scene. In addition, objects may be synchronized with each other. User interactions may also prohibit a straightforward parallelization. We propose a modeling methodology that captures the spatio-temporal relationship between various objects and user interaction. We then propose a number of scheduling algorithms that periodically allocate MPEG-4 objects to multiple workstations ensuring load balancing and synchronization requirements among multiple objects. Each scheduling algorithm has its own performance and complexity characteristics. The experimental results, while showing real-time encoding rates, exhibit tradeoffs between load balancing, scheduling overhead cost, and global performance.

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.

In the area of parallelizing compilers, considerable research has been carried out on data dependency analysis, parallelism extraction, as well as program and data partitioning. However, designing a practical, low complexity scheduling algorithm without sacrificing performance remains a challenging problem. A variety of heuristics have been proposed to generate efficient solutions but they take prohibitively long execution times for moderate size or large problems. In this paper, we propose an algorithm called FASTEST (Fast Assignment and Scheduling of Tasks using an Efficient Search Technique) that has O(e) time complexity, where e is the number of edges in the task graph. The algorithm first generates an initial solution in a short time and then refines it by using a simple but robust random neighborhood search. We have also parallelized the search to further lower the time complexity. We are using the algorithm in a prototype automatic parallelization and scheduling tool which compiles sequential code and generates parallel code optimized with judicious scheduling. The proposed algorithm is evaluated with several application programs and outperforms a number of previous algorithms by generating parallelized code with shorter execution times, while taking dramatically shorter scheduling times. The FASTEST algorithm generates optimal solutions for a majority of the test cases and close-to-optimal solutions for the rest.

Many World Wide Web applications require access to and the transfer and synchronization of large multimedia data objects (MDOs), such as audio, video and images, across the communication network. The transfer of large MDOs contributes to the response time observed by the end users. As the end users expect strict adherence to response time constraints, the problem of allocating these MDOs so as to minimize response time becomes very challenging. The problem becomes more complex in the context of hypermedia documents (Web pages), wherein these MDOs need to be synchronized during presentation to the end users. Since the basic problem of data allocation in distributed database systems is NP-complete, a need exists to pursue and evaluate solutions based on heuristics for generating near-optimal MDO allocations. In this paper, we (i) conceptualize this problem by using a navigational model to represent hypermedia documents and their access behavior by end users, (ii) formulate the problem by developing a base case cost model for response time, (iii) design two algorithms to find near-optimal solutions for allocating MDOs of the hypermedia documents while adhering to the synchronization requirements, and (iv) evaluate the trade-off between the time complexity to obtain the solution and the quality of the solution by comparing the algorithms' solutions with an exhaustive solution over a set of experiments.

Obtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose search-based algorithms for determining optimal schedules for moderately large problem sizes. The first algorithm which is based on the A* search technique uses a computationally efficient cost function for guiding the search with reduced complexity. We propose a number of state-pruning techniques to reduce the size of the search space. For further lowering the complexity, we parallelize the search. The parallel version is based on reduced interprocessor communication and is guided by static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but takes considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions for medium to moderately large problems while the approximate algorithm is a useful alternative if slightly degraded solutions are acceptable.

MPEG-4 which is currently being developed by MPEG (Moving Pictures Experts Group), is poised to become a standard for supporting current and emerging interactive multimedia applications. The objective of MPEG-4 is to support content-based compression, communication, access and manipulation of digital objects which can be natural or synthetic. Since MPEG-4 based video consists of objects and provides full interactivity between the client and the server, a software-based implementation seems to be the only viable approach for building an MPEG-4 encoder. Parallel processing solves the problem of large computational requirements for building a real-time encoder. In this paper, we describe a parallel implementation of MPEG-4 video encoder using a cluster of workstations collectively working as a virtual machine. Parallelization of the MPEG-4 encoder poses an interesting problem since not only can objects be added or deleted from a video scene but their sizes and shapes may vary with time. Moreover, some of the computationally intensive parts of the encoder are non-uniform algorithms, which means their execution times are data dependent and cannot be predicted in advance. In order to guarantee the spatio-temporal relationship between various objects in a video, we propose a real-time scheduling algorithm for exploiting parallelism in the temporal domain. The algorithm divides the workstations into a number of groups and assigns one video object to one group of workstations for encoding. A dynamic shape-adaptive data partitioning strategy is proposed to exploit parallelism in the spatial domain. The partitioning strategy divides the data of an object among the workstations within a group. The scheduling scheme ensures the synchronization requirements among multiple objects while the dynamic data parallel approach adapts to the object shape variations to balance the load for all the workstations. The performance of the encoder can scale according to the number of workstations used. With 20 workstations, the encoder yields an encoding rate higher than real-time, allowing to encode multiple sequences simultaneously.

A major cost in executing queries in a distributed database system is the data transfer cost incurred in transferring relations (fragments) accessed by a query from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the fragments at different sites so as to minimize the total data transfer cost incurred in executing a set of queries. This is equivalent to minimizing the average query execution time, which is of primary importance in a wide class of distributed systems. The data allocation problem, however, is NP-complete, and thus requires fast heuristics to generate efficient solutions. The problem becomes more complex in the context of hypermedia documents (Web pages), within which the multimedia data objects (MDOs) need to be synchronized during presentation to the end users. Since the basic problem of data allocation in distributed database systems is NP-complete, we need heuristics which can generate near-optimal MDO allocations. In this paper, we propose a navigational model to represent hypermedia documents and their access behaviour from end users. We also formulate the problem by developing a base-case cost model for the response time, and we design an algorithm to find near-optimal solutions for allocating MDOs of the hypermedia documents while adhering to the synchronization requirements. We compare the algorithmic solution with an exhaustive solution over a set of experiments.

We describe a software-based MPEG4 video encoder which is implemented using parallel processing on a cluster of workstations collectively working as a virtual machine. The contributions of our work are as follows. First, a hierarchical Petri-nets-based modeling methodology is proposed to capture the spatiotemporal relationships among multiple objects at different levels of an MPEG-4 video sequence. Second, a scheduling algorithm is proposed to assign video objects to workstations for encoding in parallel. The algorithm determines the execution order of video objects, ensures that the synchronization requirements among them are enforced and that presentation deadlines are met. Third, a dynamic partitioning scheme is proposed which divides an object among multiple workstations to extract additional parallelism. The scheme achieves load balancing among the workstations with a low overhead. The striking feature of our encoder is that it adjusts the allocation and partitioning of objects automatically according to the dynamic variations in the video object behavior. We have made various additional software optimizations to further speed up the computation. The performance of the encoder can scale according to the number of workstations used. With 20 workstations, the encoder yields an encoding rate higher than real time, allowing the encoding of multiple sequences simultaneously.

One of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous algorithms.

The lack of a versatile software tool for parallel program development has been one of the major obstacles for exploiting the potential of high-performance architectures. In this paper, we describe an experimental software tool called CASCH (Computer Aided SCHeduling) for parallelizing and scheduling applications to parallel processors. CASCH transforms a sequential program to a parallel program with automatic scheduling, mapping, communication, and synchronization. The major strength of CASCH is its extensive library of scheduling and mapping algorithms representing a broad range of state-of-the-art work reported in the recent literature. These algorithms are applied for allocating a parallelized program to the processors, and thus the algorithms can be interactively analyzed, tested and compared using real data on a common platform with various performance objectives. CASCH is useful for both novice and expert programmers of parallel machines, and can serve as a teaching and learning aid for understanding scheduling and mapping algorithms.

Video encoding due to its high processing requirements has been traditionally done using special-purpose hardware. Software solutions have been explored but are considered to be feasible only for nonreal-time applications requiring low encoding rates. However, a software solution using a general-purpose computing system has numerous advantages: it is more available and flexible and allows experimenting with and hence improving various components of the encoder. In this paper, we present the performance of a software video encoder with MPEG-2 quality on various parallel and distributed platforms. The platforms include an Intel Paragon XP/S and an Intel iPSC/860 hypercube parallel computer as well as various networked clusters of workstations. Our encoder is portable across these platforms and uses a data-parallel approach in which parallelism is achieved by distributing each frame across the processors. The encoder is useful for both real-time and nonreal-time applications, and its performance scales according to the available number of processors. In addition, the encoder provides control over various parameters such as the size of the motion search window, buffer management, and bit rate. The performance results include comparisons of execution times, speedups, and frame encoding rates on various systems.

Distributed systems such as networks of workstations are becoming an increasingly viable alternative to traditional supercomputer systems for running complex scientific applications. A large number of these applications require solving sets of partial differential equations (PDEs). In this paper, we describe the implementation and performance of SPEED (Scalable Partial differential Equation Environment on Distributed systems), a parallel platform which provides an efficient solution for time-dependent PDEs. SPEED allows the inclusion of a wide range of parameters and programming aids. PVM is employed as the underlying message-passing system. The parallel implementation has been performed using two algorithms. The first algorithm is a two-phase scheme which uses the conventional technique of alternating phases of computation and communication. The second algorithm employs a pre-computation technique that allows overlapping of computation and communication. Both methods yield significant speedups. The pre-computation technique reduces the communication time between the workstations but incurs additional overhead in buffer management. Hence, if the saving in communication time is larger than the overhead, the pre-computation technique outperforms the two-phase algorithm. SPEED also provides a performance prediction methodology that can accurately predict the performance of a given application on the system before running the application. This methodology allows the user to tune various parameters in order to identify system bottlenecks and maximize the performance.

A major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDOs) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDOs at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. The optimal allocation of MDOs depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. We fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDOs accessed by a query. Given the MDO dependency graphs as well as the set of multimedia database sites, data transfer costs between the sites, the allocation limit on the number of MDOs that can be allocated at a site, and the query execution frequencies from the sites, an allocation scheme is generated. We formulate the data allocation problem as an optimization problem. We solve this problem with a number of techniques that broadly belong to three classes: max-flow min-cut, state-space search, and graph partitioning heuristics. The max-flow min-cut technique formulates the data allocation problem as a network-flow problem, and uses a hill-climbing approach to try to find the optimal solution. For the state-space search approach, the problem is solved using a best-first search algorithm. The graph partitioning approach uses two clustering heuristics, the agglomerative clustering and divisive clustering. We evaluate and compare these approaches, and assess their cost-performance trade-offs. All algorithms are also compared with optimal solutions obtained through exhaustive search. Conclusions are also made on the suitability of these approaches to different scenarios.

In this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures.

The paper describes the implementation and performance of a parallel platform for solving partial differential equations (PDEs) on distributed systems. The platform has been implemented using PVM for a network of workstations. It allows the inclusion of a wide range of parameters and programming aids. The PDEs are specified in the form of finite difference equations. With a given set of parameters and a partitioning strategy, the platform provides facilities to record and predict the performance of an application before running it. The performance prediction model helps the user to identify the major bottlenecks of the platform such that by reducing them, the speedup can be improved. We also present analysis of various factors that can have drastic effect on the speedup, which allows the user to tune a number of parameters to maximize the performance.

The use of a network of workstations as a single unit for speeding up computationally intensive applications is becoming a cost-effective alternative to traditional parallel computers. We present the implementation of an application-driven parallel platform for solving partial differential equations (PDEs) on this computing environment. The platform provides a general and efficient parallel solution for time-dependent PDEs and an easy-to-use interface that allows the inclusion of a wide range of parallel programming tools. We have used two different parallelization methods in this platform. The first method is a two-phase algorithm which uses the conventional technique of alternating computation and communication phases. The second method uses a novel pre-computation technique which allows overlapping of computation and communication. Both methods yield significant speedup. However the pre-computation technique is shown to be more efficient and scalable.>

In this paper, we explore the problem of scheduling parallel programs using task duplication for message-passing multicomputers. Task duplication means scheduling a parallel program by redundantly executing some of the tasks on which other tasks of the program critically depend. This can reduce the start times of tasks waiting for messages from tasks residing in other processors. There have been a few scheduling algorithms using task duplication. We discuss two such previously reported algorithms and describe their differences, limitations and suitability for different environments. A new algorithm is proposed which outperforms both of these algorithms, and is more efficient for low as well as high values of communication-to-computation ratios. The algorithm takes into account arbitrary computation and communication costs. All three algorithms are tested by scheduling some of the commonly encountered graph structures.

An algorithm for compile-time static scheduling of task graphs onto multiprocessors is proposed. The proposed algorithm, which is called Dynamic Critical Path (DCP) scheduling algorithm, is different from previously reported algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it uses an intelligent way to select a suitable processor for a node by looking ahead the potential start times of the remaining critical nodes on that processor and by scheduling relatively less important nodes to the processors already in use. Four related scheduling algorithms are also discussed. Although these algorithms are efficient in general, they possess drawbacks which can lead to poor performance. The proposed DCP algorithm overcomes the drawbacks of these algorithms and outperforms them by a considerable margin. Despite having a number of new features, the DCP algorithm is fast, efficient in terms of the number of processors used and is equally suitable for different types of graph structures.

Abstract The paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load‐balancing strategies. A distributed multicomputer system using distributed load‐balancing strategies is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back‐propagation learning algorithm based on gradient descent The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is very effective in predicting the performance of dynamic load‐balancing algorithms. Our work leads to interesting techniques for designing load balancing schemes (for large distributed systems) that are computationally very expensive to simulate. One of the important findings is that performance is affected least by the number of nodes, and most by the number of links at each node in a large distributed system.

In this paper a hierarchical task scheduling strategy for assigning parallel computations with dynamic structures to large hypercube multicomputers is proposed. Such computations represent a wide range of recursive and divide/conquer algorithms for which structure of the problem varies dynamically. To achieve load balancing and reduce processor contentions, the system is divided into multiple regions of processors for which the first level of scheduling is done by the host computer that spreads out the initial computations into these regions. The second level scheduling is done by a set of median processors of these regions which enable the processors of their regions to optimally balance the dynamically created load and to communicate with each other with reduced overhead. The results of an extensive simulation study are presented that exhibit the performance of the proposed strategy under different loading conditions, varying degrees of depth and parallelism, and communication costs. The proposed dual-level hierarchical scheduling is shown to outperform a well known distributed scheduling strategy.

For managing tasks efficiently in a Distributed Het erogeneous Supercomputing System (DHSS) , we re quire a thorough understanding of applications and their intelligent scheduling within the system. For this purpose, an accurate estimation of the execu tion time of applications on various architectures is needed. In this paper we present a framework to ad dress this issue. We propose two techniques, called augmented code profiling and augmented analytical benchmarking, to characterize applications and archi tectures in a DHSS, respectively. These techniques are based on code profiling and analytical benchmarking, respectively and provide a detailed architectural-dependent characterization of DHSS applications.

A dual-level dynamic load distribution strategy is proposed for allocating parallel computations with unpredictable structures to hypercube based distributed systems. Computations with dynamic structures represent a wide range of recursive and divide/conquer algorithms. The allocation strategy supports dynamic partitioning of these computations into communicating sub-tasks. Using the topological characteristics of hypercube networks, the system is divided into multiple regions of processors. The first level allocation is done by the central computer that spreads out the initial computations into these regions to reduce processor contention. The second level allocation is done by the median processors of these regions which enable the processors of their regions to optimally balance the dynamically created load and to communicate with each other with reduced overhead. The results of a simulation study are presented illustrating numerous examples that exhibit the performance of the proposed strategy under different loading conditions, varying degrees of depth and parallelism in the task graphs. The proposed allocation strategy is shown to outperform distributed load distribution.>

The authors present a scheme for managing real-time task allocation and load redistribution with fault-tolerance for hypercube systems. A set of processors, called fault-control processors (FCPs), can be used for keeping the duplicate copies of tasks and real locating tasks if the original processors of those tasks fail. Two-level task redundancy is used by grouping the FCPs as primary and secondary for each processor. The proposed scheme provides a high degree of fault-tolerance since each FCP itself is monitored by other FCPs. Assuming a failure-repair system environment, the performance of the proposed strategy has been evaluated and compared with a fault-free environment for 256-node and 512-node hypercubes, through simulation experiments. The authors also introduce a measure of goodness, success probability, which represents the probability of reallocated tasks meeting their deadlines despite the failures of processors. It is shown that, using the proposed scheme, a large percentage of the rescheduled tasks can still meet their deadlines. The probability of a task being lost altogether, due to multiple failures, has been shown to be extremely low.>

Thispaperpresents aperformance evaluation approachto compare different distributed load balancing schemes on

A semidistributed approach is given for load balancing in large parallel and distributed systems which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. The authors consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and, using their algebraic characteristics, show that identification of spheres and their scheduling points is in general an NP-complete problem. An efficient solution for this problem is presented by making exclusive use of a combinatorial structure known as the Hadamard matrix. The performance of the proposed strategy has been evaluated and compared with an efficient fully distributed strategy through an extensive simulation study. The proposed strategy yielded much better results.>

The authors propose a distributed task scheduling model using a simple processor architecture and a heuristic scheduling algorithm based on small message exchanges between nearest neighbors. An extensive simulation study was used to analyze the proposed model by taking into account a wide range of practical issues. Comparison with other schemes reported in the literature reveals the superiority of the proposed model in terms of various performance measures. The scheduling algorithm supported by some software components improves the response time to a great extent by trying to keep the network nodes equally busy. The exchange of load status information has low complexity. An interesting trade-off between periodic update and non-periodic information update is exhibited. The performance of the proposed algorithms does not degrade when no transfer limit is used. The communication rate of the network has a major influence on the performance but it is shown that further reduction in response time cannot be achieved after a certain increase in communication rate. Simulation experiments on various network topologies showed the adaptive nature of the proposed algorithms.>

The authors present a semi-distributed approach for task scheduling in large parallel and distributed systems which is different from the conventional centralized and fully distributed approaches. The proposed strategy partitions the system into independent regions (spheres) centered at some control points. The central points, called schedulers optimally schedule tasks within their spheres and maintain state information with low overhead. The authors consider hypercube systems for evaluation and, using their algebraic characteristics, show that identification of spheres and their scheduling points is an NP-complete problem. The performance of the proposed strategy was evaluated and compared with an efficient fully distributed strategy. In addition to yielding high performance in terms of response time, better resource utilization, and throughput, the proposed strategy is shown to incur small overhead in terms of network traffic.>