Search

Encyclopedias of regulatory genomic elements provide a foundation for research in areas such as disease diagnosis, disease treatment, and crop enhancement. The construction of complete encyclopedias of organism-specific genomic elements involved in gene regulation remains a significant challenge. To address this problem, the authors present novel bioinformatics strategies for exploring the word landscapes of putative regulatory regions of genomes. The methods are incorporated into the WordSeeker software tool, which is available at http://word-seeker.org. The effectiveness of these strategies is demonstrated through several case studies.

The primary purpose of SiteSeeker is to create a workbench to try out various concepts for discovery strategies and motif scoring. The intention was to develop a tool that enables testing of different concepts regarding combined scoring methods and search strategies, that eventually ends in tool of practical use.

Dynamic real-time systems require adaptive resource management to accommodate varying processing needs. This paper addresses the problem of resource management on a single resource for soft real-time systems (no hard deadline requirements) consisting of tasks that have discrete quality of service (QoS) settings that correspond to varying resource requirements and varying utility. Our approach employs a feedback architecture wherein task QoS settings are adjusted on-line in order to maintain a desired amount of resource slack. These adjustments are calculated based on incremental changes in resource slack using computationally efficient algorithms that provide nearly optimal utility with computable performance bounds. The feedback architecture provides robustness in the presence of additional resource load and imperfect task resource requirement specifications.

Some distributed real-time systems interact with external environments that change dynamically, and it is necessary to take the external variables into account when performing task allocation. We developed an approximation algorithm for task allocation, and it finds allocations that are maximally robust against dynamic changes in multiple external variables. Such an algorithm will help to reduce expensive reallocations triggered by changes in unpredictable environments. The algorithm has a polynomial running time, and its robustness optimality is given by an approximation ratio, which equals 2.41 asymptotically, when workloads are large and workload independent utilization of tasks is insignificant

The growth of load balancing system raises the issue of scalability, and decentralized load balancing architecture has been proposed to address this issue. In this paper, we investigate how a load balancing architecture can be built on decentralized policies based on CORBA and enhanced by predictive algorithm. The L/sub 2/E predictive filtering model was used to supply workstations with robust cluster load information, which allows them to make more accurate independent allocation decisions. Experimental results showed that our decentralized load balancing approach was able to suppress thrashing and oscillations compared to other load monitoring and prediction techniques, and it was able to achieve a highly balanced system than Sun Grid Engine.

This paper extends the previous work on the maximal allowable workload (MAW) problem [D. Juedes et al., (2004)] by investigating a resource allocation problem for distributed real-time systems that contain replicable applications. The systems may use multiple resources of a single type and be affected by multiple environmental factors. The approach searches for a feasible allocation that maximizes a user defined metric of stability. Several algorithms were developed and experiments were conducted to demonstrate the relative strength of these algorithms. The results showed that simulated annealing provides results that are the closest to the optimal for maximizing environmental parameter settings. In addition modified greedy first fit is shown to be the best performing algorithm for finding feasible allocations.

Integration of middleware scheduling and resource management services enables open distributed real-time embedded (DRE) applications to meet end-to-end quality of service (QoS) requirements in highly variable operating environments. This paper describes our research on integrating CORBA scheduling and resource management services, and presents experiments we conducted to validate and quantify the benefits of this integration. Our experimental results show that integrating distributed scheduling and resource management in middleware for open DRE systems can offer significant improvements in predictability. Specifically, integrating our stand-alone resource management service with a previously unmanaged experimental baseline application reduced the ratio of missed deadlines from 26% to 10%, and the same application performed even better under the control of integrated scheduling and resource management services, with a missed deadline ratio of only 1%.

Summary form only given. We propose architecture and a general optimization framework for dynamic, distributed real-time systems. Interesting features of this model include the consideration of adaptive applications and utility functions. We extend by formalizing the corresponding multicriterial optimization problem. As the most difficult part of this problem, we identified the evaluation and comparison of the quality of single allocations and sets of allocations, respectively. To this end, we propose and examine metrics for measuring the goodness of solutions within our general resource management framework. These metrics lay the basis for further work on developing both online and offline algorithms to tackle the general optimization problem and provide an efficient adaptive resource manager for dynamic, distributed real-time systems.

Summary form only given. We describe the quality-based adaptive resource management architecture, QARMA, a framework for resource management within CORBA. QARMA consists of three major components: the system repository service, the resource management service, and the enactor service. QARMA serves as a basis for integration of existing CORBA services and management mechanisms into a single, coherent framework for resource management. QARMA supports the management of a wide variety of applications developed using various development paradigms, easily integrates with other management and infrastructure components that already exist as CORBA services, and is easily extended to allow the use of new resource management mechanisms as they become available.

Summary form only given. We examine several heuristic algorithms for the maximum allowable workload (MAW) problem for real-time systems with tasks having variable workloads. Briefly, the problem concerns the allocation of tasks to m processors, where each task t is characterized by a function t.r(w) that gives the running time of the task in terms of its workload (or input size) w. The objective of the maximum allowable workload problem is to find an allocation of tasks to processors so that the allocation is feasible (no task misses its deadline) when each task is given a workload of w or smaller and w is maximized. This optimization problem uses a robustness measure that is closely related to the MAIL (maximum allowable increase in load) metric recently proposed by Gertphol et al. The main contribution of this paper is the comparison of several heuristic algorithms for the MAW-RMS problem. Hillclimbing, random search, simulated annealing, and first-fit heuristics are presented and evaluated via simulation. As we show here, the first-fit greedy heuristic produces solutions of a reasonable quality compared to the other algorithms. In addition, we demonstrate the applicability of our model in air defense systems.

A framework for analyzing resource usage of distributed periodic processes specified in RT-Chart is provided. Functions for reasoning about the quality of an assignment of processes to computation nodes are developed, and a novel model of resource use costs and communication costs is shown. The model allows reasoning about the rates of progress each action makes when using its resources, thus modeling contention among periodic processes sharing a resource. The computed rates of progress are accurate since impossible sources of resource contention are removed. These are useful techniques for assignment algorithms (such as simulated annealing) that repeatedly reassign actions until a close-to-optimal solution is obtained. >

The authors apply random neural networks to the problem of assigning abstract data type modules (ADTs) to the processing elements of parallel computers. Although assignment of tasks has been discussed extensively in the literature, the automatic assignment of ADTs is a relatively new problem, and therefore they describe the problem in detail. This is followed by an introduction to the random neural network model and a presentation of the neural network solution to the assignment problem. Experimental results are presented comparing the solution to those obtained with random assignment and with a greedy heuristic. The random neural network is found to give significantly better results than the other two approaches in virtually every case. >

Certain real-time applications must operate in highly dynamic environments, thereby precluding accurate characterization of the applications' workloads by static models. Thus, guarantees of real-time performance based on a priori characterizations are not possible. However, potential benefits of a posteriori approaches are significant, including the ability to function correctly in dynamic environments (through adaptability to unforeseen conditions), and higher actual utilization of computing resources. In this paper, we consider a control theoretic framework that is appropriate for systems which experience large variations in workload. The goal is to manage a distributed collection of computing resources by continuously computing and assessing QoS and resource utilization metrics that are determined a posteriori. Potential benefits of developing a control theoretic framework for resource management include: reuse of the large body of results in control theory, focus on problem characteristics instead of control infrastructures, and stability analysis.

Schedulability Analysis (SA) approaches that are based on a priori information and use fixed execution times with constant workloads work well in many application domains and allow pre-deployment guarantees of real-time performance such as Rate Monotonic Analysis (RMA [2]). However, certain realtime applications must operate in highly dynamic environments, thereby precluding accurate characterization of workloads by static models. This leads to the notion that a new SA trigger for dynamic environments, in which applications experience large variations in the workload, needs to guarantee real-time performance during run-time. This paper examines the case of periodic, dynamic real-time systems, and describes an efficient SA policing technique which can trigger SA appropriately, and uses a dynamic threshold which becomes sensitive when the quality of service (QoS) of the dynamic real-time application approaches its deadline.

Researchers are currently investigating applying benefit, or utility functions for allocating resources in limited, soft real time systems [1,2,3]. While the future of real-time computing research and practice will likely exploit the utility of benefit-based models, this will not occur until a suitable system level benefit framework has been defined. This paper provides an overview of ongoing work to develop such an initial framework that can formalize the use of benefit functions in complex real time systems. It is easily shown that this framework can support traditional hard/firm/soft real-time paradigms as well as support newer proposed models for future real time operation [5,6]. We also show that our proposed framework unifies composition of benefit values derived from heterogeneous perspectives, including those derived from the application perspective.

Breakthrough in Earth Science Observing will occur when constellations of Earth observing satellites are able to fully collaborate together and collectively monitor the conditions of our planet through a vast array of instruments. These satellites form a network that consists of distributed processes that need to respond to perceived scientific events, the spacecraft environment, spacecraft anomalies and user commands. The requests and responses exhibit dynamic behavior. In order to handle such dynamic environments, a method is needed to guarantee the real-time quality of service constraints. The DeSiDeRaTa resource management approach is being enhanced to characterize the dynamic aspects of intraconstellation topologies and to accommodate the concept of service levels and utility.This paper presents a design model of cooperative problem solving to show how the solution approach addresses the key challenges presented in the problem and specifies how the agent, resource manager and satellite constellations would operate correctly and interact in complex, dynamic and unpredictable environments. It extends the system model of DeSiDeRaTa to accommodate the concepts of utility, service levels and planning. The system model for the IPA is presented to show the proof of concept.

This paper presents our design and tests of a realtime network monitoring program for DeSiDeRaTa, an existing resource management system. This monitor will assist DeSiDeRaTa in maintaining an acceptable Quality of Service (QoS) for groups of real-time applications by reporting the communication delays caused by inadequate network bandwidth. The network monitoring application we developed uses SNMP and network topology information gleaned from the DeSiDeRaTa application specification files. Network bandwidth utilization of each real-time communication path is computed, and experiments have been run to demonstrate the accuracy of these measurements.