%0 Conference Paper %B 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW) %D 2011 %T A Model-Based Schedule Representation for Heterogeneous Mapping of Dataflow Graphs %A Wu, Hsiang-Huang %A Chung-Ching Shen %A Sane, N. %A Plishker,W. %A Bhattacharyya, Shuvra S. %K Computational modeling %K data flow graphs %K dataflow schedule graph %K dataflow semantics %K dataflow-based application specifications %K Dynamic scheduling %K heterogeneous mapping %K heterogeneous signal processing system design %K model-based design methodologies %K model-based schedule representation %K Processor scheduling %K Program processors %K Schedules %K semantics %K Signal processing %K synchronization %X Dataflow-based application specifications are widely used in model-based design methodologies for signal processing systems. In this paper, we develop a new model called the dataflow schedule graph (DSG) for representing a broad class of dataflow graph schedules. The DSG provides a graphical representation of schedules based on dataflow semantics. In conventional approaches, applications are represented using dataflow graphs, whereas schedules for the graphs are represented using specialized notations, such as various kinds of sequences or looping constructs. In contrast, the DSG approach employs dataflow graphs for representing both application models and schedules that are derived from them. Our DSG approach provides a precise, formal framework for unambiguously representing, analyzing, manipulating, and interchanging schedules. We develop detailed formulations of the DSG representation, and present examples and experimental results that demonstrate the utility of DSGs in the context of heterogeneous signal processing system design. %B 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW) %P 70 - 81 %8 2011 %G eng %0 Conference Paper %B 2011 IEEE Workshop on Signal Processing Systems (SiPS) %D 2011 %T Vectorization and mapping of software defined radio applications on heterogeneous multi-processor platforms %A Zaki, G.F. %A Plishker,W. %A Bhattacharyya, Shuvra S. %A Clancy, C. %A Kuykendall, J. %K Benchmark testing %K block processing %K Design methodology %K formal description %K GNU radio environment %K Graphic Processor Unit %K Graphics processing unit %K heterogeneous multiprocessor platform %K mapping problem %K Multicore processing %K Multiprocessing systems %K multiprocessor architecture %K multiprocessor scheduling %K operating systems (computers) %K PARALLEL PROCESSING %K Processor scheduling %K Schedules %K SIMD core %K Software Defined Radio %K software defined radio system design %K software radio %K telecommunication computing %K Throughput %K vectorization %K workflow %X A variety of multiprocessor architectures have proliferated even for off-the-shelf computing platforms. To improve performance and productivity for common heterogeneous systems, we have developed a workflow to generate efficient solutions. By starting with a formal description of an application and the mapping problem we are able to generate a range of designs that efficiently trade-of latency and throughput. In this approach, efficient utilization of SIMD cores is achieved by applying extensive block processing in conjunction with efficient mapping and scheduling. We demonstrate our approach through an integration into the GNU Radio environment for software defined radio system design. %B 2011 IEEE Workshop on Signal Processing Systems (SiPS) %P 31 - 36 %8 2011 %G eng %0 Conference Paper %B 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW) %D 2010 %T Decentralized dynamic scheduling across heterogeneous multi-core desktop grids %A Jaehwan Lee %A Keleher,P. %A Sussman, Alan %K backfill jobs %K bounded waiting time %K Computer science %K decentralized dynamic scheduling %K desktop grid resource management %K Dynamic scheduling %K Educational institutions %K Environmental management %K grid computing %K heterogeneous multicore desktop grid %K job assignment %K job migration %K load balancing %K Load management %K multicore computing environment %K Peer to peer computing %K Processor scheduling %K residual resources %K resource allocation %K Resource management %K scheduling %K Scheduling algorithm %K Throughput %X The recent advent of multi-core computing environments increases both the heterogeneity and complexity of managing desktop grid resources, making efficient load balancing challenging even for a centralized manager. Even with good initial job assignments, dynamic scheduling is still needed to adapt to dynamic environments, as well as for applications whose running times are not known a priori. In this paper, we propose new decentralized scheduling schemes that backfill jobs locally and dynamically migrate waiting jobs across nodes to leverage residual resources, while guaranteeing bounded waiting times for all jobs. The methods attempt to maximize total throughput while balancing load across available grid resources. Experimental results via simulation show that our scheduling scheme has performance competitive with an online centralized scheduler. %B 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW) %I IEEE %P 1 - 9 %8 2010/04/19/23 %@ 978-1-4244-6533-0 %G eng %R 10.1109/IPDPSW.2010.5470877 %0 Conference Paper %B 2010 21st IEEE International Conference on Application-specific Systems Architectures and Processors (ASAP) %D 2010 %T Loop transformations for interface-based hierarchies IN SDF graphs %A Piat, J. %A Bhattacharyya, Shuvra S. %A Raulet, M. %K Application software %K code generation %K Computer architecture %K Computer interfaces %K Data-Flow programming %K Digital signal processing %K Loop parallelization %K PARALLEL PROCESSING %K Power engineering computing %K Power system modeling %K Processor scheduling %K Programming profession %K scheduling %K SDF graph %K system recovery %X Data-flow has proven to be an attractive computation model for programming digital signal processing (DSP) applications. A restricted version of data-flow, termed synchronous data-flow (SDF), offers strong compile-time predictability properties, but has limited expressive power. A new type of hierarchy (Interface-based SDF) has been proposed allowing more expressivity while maintaining its predictability. One of the main problems with this hierarchical SDF model is the lack of trade-off between parallelism and network clustering. This paper presents a systematic method for applying an important class of loop transformation techniques in the context of interface-based SDF semantics. The resulting approach provides novel capabilities for integrating parallelism extraction properties of the targeted loop transformations with the useful modeling, analysis, and code reuse properties provided by SDF. %B 2010 21st IEEE International Conference on Application-specific Systems Architectures and Processors (ASAP) %P 341 - 344 %8 2010 %G eng %0 Conference Paper %B 2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP) %D 2010 %T Simulating dynamic communication systems using the core functional dataflow model %A Sane, N. %A Chia-Jui Hsu %A Pino,J. L %A Bhattacharyya, Shuvra S. %K adaptive modulation %K Analytical models %K Application software %K Computational modeling %K core functional dataflow model %K Dataflow %K dataflow modeling semantics %K design tools %K Digital signal processing %K dynamic communication systems %K functional specification %K Hardware %K modeling and simulation %K Power system modeling %K Predictive models %K Processor scheduling %K Production %K Signal processing %K software tools %K wireless communication %X The latest communication technologies invariably consist of modules with dynamic behavior. There exists a number of design tools for communication system design with their foundation in dataflow modeling semantics. These tools must not only support the functional specification of dynamic communication modules and subsystems but also provide accurate estimation of resource requirements for efficient simulation and implementation. We explore this trade-off - between flexible specification of dynamic behavior and accurate estimation of resource requirements - using a representative application employing an adaptive modulation scheme. We propose an approach for precise modeling of such applications based on a recently-introduced form of dynamic dataflow called core functional dataflow. From our proposed modeling approach, we show how parameterized looped schedules can be generated and analyzed to simulate applications with low run-time overhead as well as guaranteed bounded memory execution. We demonstrate our approach using the Advanced Design System from Agilent Technologies, Inc., which is a commercial tool for design and simulation of communication systems. %B 2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP) %P 1538 - 1541 %8 2010 %G eng %0 Conference Paper %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %D 2008 %T Capacity of Asynchronous Random-Access Scheduling in Wireless Networks %A Chafekar,D. %A Levin,D. %A Kumar,V. S.A %A Marathe,M. V %A Parthasarathy,S. %A Srinivasan, Aravind %K asynchronous random-access scheduling %K channel access probability %K Computer networks %K Computer science %K Educational institutions %K Interference %K Optimal scheduling %K Peer to peer computing %K probability %K Processor scheduling %K radio link %K radio links %K radio networks %K Routing %K scheduling %K Throughput %K throughput capacity %K wireless channels %K Wireless networks %X We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models. %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %I IEEE %P 1148 - 1156 %8 2008/04/13/18 %@ 978-1-4244-2025-4 %G eng %R 10.1109/INFOCOM.2008.170 %0 Conference Paper %B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008 %D 2008 %T Network-Aware Join Processing in Global-Scale Database Federations %A Xiaodan Wang %A Burns,R. %A Terzis,A. %A Deshpande, Amol %K Astronomy %K Computer networks %K Concurrent computing %K global-scale database federations %K join scheduling algorithms %K network utilization %K network-aware join processing %K parallel schedules %K polynomial-time algorithm %K Polynomials %K Processor scheduling %K Query processing %K reduce resource usage %K Scheduling algorithm %K Spatial databases %K spatial-join queries %K Telecommunication traffic %K Throughput %X We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery's users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead. %B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008 %I IEEE %P 586 - 595 %8 2008/04/07/12 %@ 978-1-4244-1836-7 %G eng %R 10.1109/ICDE.2008.4497467 %0 Journal Article %J IEEE Transactions on Signal Processing %D 2006 %T Contention-conscious transaction ordering in multiprocessor DSP systems %A Khandelia,M. %A Bambha,N. K %A Bhattacharyya, Shuvra S. %K contention-conscious transaction ordering %K Costs %K data flow graphs %K Dataflow %K Delay %K Digital signal processing %K digital signal processing chips %K Embedded system %K graph-theoretic analysis %K Instruments %K Internet telephony %K interprocessor communication %K iterative dataflow graphs %K iterative methods %K Message passing %K multiprocessor %K multiprocessor DSP systems %K NP-complete problem %K Processor scheduling %K scheduling %K Signal processing %K synchronization %K Throughput %X This paper explores the problem of efficiently ordering interprocessor communication (IPC) operations in statically scheduled multiprocessors for iterative dataflow graphs. In most digital signal processing (DSP) applications, the throughput of the system is significantly affected by communication costs. By explicitly modeling these costs within an effective graph-theoretic analysis framework, we show that ordered transaction schedules can significantly outperform self-timed schedules even when synchronization costs are low. However, we also show that when communication latencies are nonnegligible, finding an optimal transaction order given a static schedule is an NP-complete problem, and that this intractability holds both under iterative and noniterative execution. We develop new heuristics for finding efficient transaction orders, and perform an extensive experimental comparison to gauge the performance of these heuristics. %B IEEE Transactions on Signal Processing %V 54 %P 556 - 569 %8 2006/02// %@ 1053-587X %G eng %N 2 %R 10.1109/TSP.2005.861074 %0 Conference Paper %B 2006 International Conference on Parallel Processing Workshops, 2006. ICPP 2006 Workshops %D 2006 %T Model-based OpenMP implementation of a 3D facial pose tracking system %A Saha,S. %A Chung-Ching Shen %A Chia-Jui Hsu %A Aggarwal,G. %A Veeraraghavan,A. %A Sussman, Alan %A Bhattacharyya, Shuvra S. %K 3D facial pose tracking system %K application modeling %K application program interfaces %K application scheduling %K coarse-grain dataflow graphs %K Concurrent computing %K data flow graphs %K Educational institutions %K face recognition %K IMAGE PROCESSING %K image processing applications %K Inference algorithms %K Message passing %K OpenMP platform %K parallel implementation %K PARALLEL PROCESSING %K parallel programming %K Particle tracking %K Processor scheduling %K SHAPE %K shared memory systems %K shared-memory systems %K Solid modeling %K tracking %X Most image processing applications are characterized by computation-intensive operations, and high memory and performance requirements. Parallelized implementation on shared-memory systems offer an attractive solution to this class of applications. However, we cannot thoroughly exploit the advantages of such architectures without proper modeling and analysis of the application. In this paper, we describe our implementation of a 3D facial pose tracking system using the OpenMP platform. Our implementation is based on a design methodology that uses coarse-grain dataflow graphs to model and schedule the application. We present our modeling approach, details of the implementation that we derived based on this modeling approach, and associated performance results. The parallelized implementation achieves significant speedup, and meets or exceeds the target frame rate under various configurations %B 2006 International Conference on Parallel Processing Workshops, 2006. ICPP 2006 Workshops %I IEEE %P 8 pp.-73 - 8 pp.-73 %8 2006/// %@ 0-7695-2637-3 %G eng %R 10.1109/ICPPW.2006.55 %0 Conference Paper %B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on %D 2005 %T CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems %A Kianzad,V. %A Bhattacharyya, Shuvra S. %A Gang Qu %K CASPER %K combined-assignment-scheduling-and-power-management %K computational complexity %K distributed system %K dynamic voltage scaling %K embedded systems %K energy reduction %K genetic algorithm %K Genetic algorithms %K graph theory %K homogeneous multiprocessor system %K maximal energy saving %K Multiprocessing systems %K multiprocessor embedded system %K optimization loop %K power management %K power variation %K Processor scheduling %K slack distribution algorithm %K task assignment %K task graph scheduling %X For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (combined assignment, scheduling, and power-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) by S. Hua and G. Qu (2005): applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm by Schmitz et al. (2004), CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA by Schmitz et al. (2002), the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop. %B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on %P 191 - 197 %8 2005/07// %G eng %R 10.1109/ASAP.2005.23 %0 Conference Paper %B Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th %D 2004 %T Achieving packet-level quality of service through scheduling in multirate WLANs %A Yuan Yuan %A Daqing Gu %A Arbaugh, William A. %A Jinyun Zhang %K Analytical models %K channel conditions %K channel errors %K channel temporal fair share %K compensation %K Computer science %K Delay %K error-prone flow compensation %K IEEE 802.11a/b/g physical layer %K multirate wireless fair scheduling %K multirate WLAN %K packet radio networks %K packet-level quality of service %K Physical layer %K Processor scheduling %K QoS %K quality of service %K radio access networks %K Scheduling algorithm %K Throughput %K throughput fairness %K USA Councils %K Wireless LAN %K wireless packet scheduling %K WMFS %X Wireless packet scheduling has been a popular paradigm to achieve packet-level QoS in terms of fairness and throughput in the presence of channel errors. However, the current design does not anticipate the multi-rate capability offered by the IEEE 802.11a/b/g physical layer, thus suffering significant performance degradation in 802.11 WLANs. In this paper, we propose multirate wireless fair scheduling (WMFS). In MWFS, each flow is granted a temporal fair share of the channel, in contrast to the throughput fair share adopted by existing algorithms. Therefore, each flow receives services in proportion to its perceived transmission rate, and high-rate flows are able to opportunistically exploit their good channel conditions and receive more services. MWFS also renovates the compensation model in order to allow for error-prone flows to catch up, thus ensuring fairness for all flows over error-prone channels. We demonstrate the effectiveness of MWFS through both simulations and analysis. Especially, WMFS achieves system throughput 159% of state-of-the-art scheduling algorithms in simulated scenarios. %B Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th %I IEEE %V 4 %P 2730- 2734 Vol. 4 - 2730- 2734 Vol. 4 %8 2004/09/26/29 %@ 0-7803-8521-7 %G eng %R 10.1109/VETECF.2004.1400554 %0 Journal Article %J IEEE Transactions on Parallel and Distributed Systems %D 2004 %T Resource policing to support fine-grain cycle stealing in networks of workstations %A Ryu, K. D %A Hollingsworth, Jeffrey K %K 65 %K Application software %K Bandwidth %K cluster computing %K Computer networks %K Computer Society %K Concurrent computing %K cycle stealing %K cycle stealing. %K grid computing %K I/O scheduling %K Intelligent networks %K Kernel %K network bandwidth %K networks of workstations %K page replacement policy %K parallel computing %K performance evaluation %K Processor scheduling %K resource allocation %K resource scheduling %K starvation-level CPU priority %K workstation clusters %K workstation resources %K Workstations %X We present the design, implementation, and performance evaluation of a suite of resource policing mechanisms that allow guest processes to efficiently and unobtrusively exploit otherwise idle workstation resources. Unlike traditional policies that harvest cycles only from unused machines, we employ fine-grained cycle stealing to exploit resources even from machines that have active users. We developed a suite of kernel extensions that enable these policies to operate without significantly impacting host processes: 1) a new starvation-level CPU priority for guest jobs, 2) a new page replacement policy that imposes hard bounds on physical memory usage by guest processes, and 3) a new I/O scheduling mechanism called rate windows that throttle guest processes' usage of I/O and network bandwidth. We evaluate both the individual impacts of each mechanism, and their utility for our fine-grain cycle stealing. %B IEEE Transactions on Parallel and Distributed Systems %V 15 %P 878 - 892 %8 2004/10// %@ 1045-9219 %G eng %N 10 %R 10.1109/TPDS.2004.58 %0 Conference Paper %B 2003 IEEE Conference on Open Architectures and Network Programming %D 2003 %T User-specified adaptive scheduling in a streaming media network %A Hicks, Michael W. %A Nagarajan,A. %A van Renesse,R. %K Adaptive scheduling %K CAMERAS %K Computer networks %K Computer science %K distributed stream processing system %K Educational institutions %K global resource scheduling %K Intelligent networks %K MediaNet %K Mobile computing %K network utilization %K Process design %K Processor scheduling %K quality of service %K Streaming media %K streaming media network %K user performance %K user-specified adaptive scheduling %X In disaster and combat situations, mobile cameras and other sensors transmit real-time data, used by many operators or analysis tools. Unfortunately, in the face of limited, unreliable resources, and varying demands, not all users may be able to get the fidelity they require. This paper describes MediaNet, a distributed stream processing system designed with the above scenarios in mind. Unlike past approaches, MediaNet's users can intuitively specify how the system should adapt based on their individual needs. MediaNet uses both local and online global resource scheduling to improve user performance and network utilization, and adapts without requiring underlying support for resource reservations. Performance experiments show that our scheduling algorithm is reasonably fast, and that user performance and network utilization are both significantly improved. %B 2003 IEEE Conference on Open Architectures and Network Programming %I IEEE %P 87 - 96 %8 2003/04/04/5 %@ 0-7803-7764-8 %G eng %R 10.1109/OPNARC.2003.1196376 %0 Conference Paper %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %D 2002 %T Dependent rounding in bipartite graphs %A Gandhi,R. %A Khuller, Samir %A Parthasarathy,S. %A Srinivasan, Aravind %K Application software %K Approximation algorithms %K bipartite graph %K bipartite graphs %K broadcast channels %K broadcast scheduling %K Broadcasting %K capacitated vertex cover %K Character generation %K computational complexity %K Computer science %K Delay %K edge-sets %K Educational institutions %K fair scheduling %K fractional vectors %K graph theory %K per-user fairness properties %K pipage rounding technique %K Processor scheduling %K Random variables %K random-graph models %K randomized rounding approach %K rounding method %K scheduling %K Scheduling algorithm %K telecommunication computing %K unrelated parallel machines %X We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties. %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %I IEEE %P 323 - 332 %8 2002/// %@ 0-7695-1822-2 %G eng %R 10.1109/SFCS.2002.1181955 %0 Conference Paper %B Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM %D 2002 %T Scheduling multiple data visualization query workloads on a shared memory machine %A Andrade,H. %A Kurc, T. %A Sussman, Alan %A Saltz, J. %K Atomic force microscopy %K Biomedical informatics %K Computer science %K Data analysis %K data visualisation %K Data visualization %K datasets %K deductive databases %K digitized microscopy image browsing %K directed graph %K directed graphs %K dynamic query scheduling model %K Educational institutions %K high workloads %K image database %K limited resources %K multiple data visualization query workloads %K multiple query optimization %K performance %K priority queue %K Processor scheduling %K Query processing %K query ranking %K Relational databases %K scheduling %K shared memory machine %K shared memory systems %K Virtual Microscope %K visual databases %X Query scheduling plays an important role when systems are faced with limited resources and high workloads. It becomes even more relevant for servers applying multiple query optimization techniques to batches of queries, in which portions of datasets as well as intermediate results are maintained in memory to speed up query evaluation. We present a dynamic query scheduling model based on a priority queue implementation using a directed graph and a strategy for ranking queries. We examine the relative performance of several ranking strategies on a shared-memory machine using two different versions of an application, called the Virtual Microscope, for browsing digitized microscopy images %B Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM %I IEEE %P 11 - 18 %8 2002/// %@ 0-7695-1573-8 %G eng %R 10.1109/IPDPS.2002.1015482 %0 Journal Article %J IEEE Transactions on Parallel and Distributed Systems %D 2000 %T Exploiting fine-grained idle periods in networks of workstations %A Kyung Dong Ryu %A Hollingsworth, Jeffrey K %K cluster of workstations %K Computer networks %K Concurrent computing %K Contracts %K Delay %K fine-grained availability %K Intelligent networks %K Linger-Longer %K networks of workstations %K PARALLEL PROCESSING %K Predictive models %K Processor scheduling %K Resumes %K scheduling policy %K Throughput %K workload characterization %K workstation clusters %K Workstations %X Studies have shown that for a significant fraction of the time, workstations are idle. In this paper, we present a new scheduling policy called Linger-Longer that exploits the fine-grained availability of workstations to run sequential and parallel jobs. We present a two-level workload characterization study and use it to simulate a cluster of workstations running our new policy. We compare two variations of our policy to two previous policies: Immediate-Eviction and Pause-and-Migrate. Our study shows that the Linger-Longer policy can improve the throughput of foreign jobs on a cluster by 60 percent with only a 0.5 percent slowdown of local jobs. For parallel computing, we show that the Linger-Longer policy outperforms reconfiguration strategies when the processor utilization by the local process is 20 percent or less in both synthetic bulk synchronous and real data-parallel applications %B IEEE Transactions on Parallel and Distributed Systems %V 11 %P 683 - 698 %8 2000/07// %@ 1045-9219 %G eng %N 7 %R 10.1109/71.877793 %0 Conference Paper %B Real-Time Systems Symposium, 1993., Proceedings. %D 1993 %T RTSL: a language for real-time schedulability analysis %A Fredette,A. N %A Cleaveland, Rance %K Algebra %K Algorithm design and analysis %K Dynamic scheduling %K Failure analysis %K finite state machines %K finite state systems %K formal logic %K formal semantics %K functional behavior %K generalized approach %K generalized schedulability analysis technique %K Process algebra %K Processor scheduling %K reachable state space %K Real time systems %K real-time schedulability analysis %K Real-Time Specification Language %K real-time systems %K RTSL %K scheduling %K Scheduling algorithm %K scheduling discipline %K Specification languages %K state-based analysis %K State-space methods %K Time factors %K Timing %K timing behavior %K timing constraints %K timing exceptions %X The paper develops a generalized approach to schedulability analysis that is mathematically founded in a process algebra called RTSL. Within RTSL one may describe the functional behavior, timing behavior, timing constraints (or deadlines), and scheduling discipline for real-time systems. The formal semantics of RTSL then allows the reachable state space of finite state systems to be automatically generated and searched for timing exceptions. We provide a generalized schedulability analysis technique to perform this state-based analysis %B Real-Time Systems Symposium, 1993., Proceedings. %I IEEE %P 274 - 283 %8 1993/12/01/3 %@ 0-8186-4480-X %G eng %R 10.1109/REAL.1993.393489