Search

Cable cranes serve as critical lifting equipment in large-scale construction projects such as dam construction, bridge building, and mining. Particularly in concrete dam construction, cable cranes are the preferred equipment for transporting concrete due to their flexible spatial moving capacity and large-span coverage. However, because of the narrow dam construction site, the intensive and concurrent transportation activities of the cable crane group are proven to cause space conflicts, resulting in low operation efficiency. Effective planning of cable crane operations is conducive to accelerating construction progress, improving the productivity of cable cranes, and ensuring a safe construction scenario. The planning of cable crane operations involves task allocation in collaborative construction (among several cable cranes) and parallel scheduling under complex spatial constraints. This paper develops an automatic planning system for cable crane operations in concrete dam construction that can directly output the optimal transportation plan of cable cranes, requiring only the input of relevant construction parameters. First, a two-sided matching model is proposed to address the task allocation problem among cable cranes. Second, a simulation model for the concrete transportation process of the cable crane group is established to solve the parallel scheduling problem and avoid collisions. Third, an improved ant colony algorithm is proposed that constructs initial solutions based on the two-sided matching model, calculates key construction indicators using the simulation model, and applies a multiobjective decision making method to find the optimal solution. Finally, an actual dam construction case validates the superiority and reliability of this proposed method. Compared with the conventional engineering approaches, the planning results of this proposed method demonstrate a 12% reduction in pouring duration and a 25% enhancement in the utilization balance of cable cranes, effectively increasing productivity and accelerating construction progress. [ABSTRACT FROM AUTHOR]

The growing development of the Internet of Things (IoT) is accelerating the emergence and growth of new IoT services and applications, which will result in massive amounts of data being generated, transmitted and processed in wireless communication networks. Mobile Edge Computing (MEC) is a desired paradigm to timely process the data from IoT for value maximization. In MEC, a number of computing-capable devices are deployed at the network edge near data sources to support edge computing, such that the long network transmission delay in cloud computing paradigm could be avoided. Since an edge device might not always have sufficient resources to process the massive amount of data, computation offloading is significantly important considering the cooperation among edge devices. However, the dynamic traffic characteristics and heterogeneous computing capabilities of edge devices challenge the offloading. In addition, different scheduling schemes might provide different computation delays to the offloaded tasks. Thus, offloading in mobile nodes and scheduling in the MEC server are coupled to determine service delay. This paper seeks to guarantee low delay for computation intensive applications by jointly optimizing the offloading and scheduling in such an MEC system. We propose a Delay-Greedy Computation Offloading (DGCO) algorithm to make offloading decisions for new tasks in distributed computing-enabled mobile devices. A Reinforcement Learning-based Parallel Scheduling (RLPS) algorithm is further designed to schedule offloaded tasks in the multi-core MEC server. With an offloading delay broadcast mechanism, the DGCO and RLPS cooperate to achieve the goal of delay-guarantee-ratio maximization. Finally, the simulation results show that our proposal can bound the end-to-end delay of various tasks. Even under slightly heavy task load, the delay-guarantee-ratio given by DGCO-RLPS can still approximate 95%, while that given by benchmarked algorithms is reduced to intolerable value. The simulation results are demonstrated the effectiveness of DGCO-RLPS for delay guarantee in MEC.

With the increasing demand for decentralized systems and the widespread usage of blockchain, low throughput and high latency have become the biggest stumbling blocks in the development of blockchain systems. This problem seriously hinders the expansion of blockchain and its application in production. Most existing smart contract scheduling solutions use static feature analysis to prevent contract conflicts during parallel execution. However, the conflicts between transactions are complex; static feature analysis is not accurate enough. In this paper, we first build the dependency between smart contracts by analyzing the features. After numerous experiments, we propose a conflict model to adjust the relationship between threads and conflict to achieve high throughput and low latency. Based on these works, we propose adaptive parallel scheduling for smart contracts on the blockchain. Our adaptive parallel scheduling can distinguish conflicts between smart contracts and dynamically adjust the execution strategy of smart contracts based on the conflict factors we define. We implement our scheme on ChainMaker, one of the most popular open-source permissioned blockchains, and build experiments to verify our solution. Regarding latency, our solution demonstrates remarkable efficiency compared with the fully parallel scheme, particularly in high-conflict transaction scenarios, where our solution achieves latency levels just one-twentieth of the fully parallel scheme. Regarding throughput, our solution significantly outperforms the fully parallel scheme, achieving 30 times higher throughput in high-conflict transaction scenarios. These results highlight the superior performance and effectiveness of our solution in addressing latency and throughput challenges, particularly in environments with high transaction conflicts. [ABSTRACT FROM AUTHOR]

This paper mainly studies a task allocation and scheduling problem in the multi-thread fulfilment process of electronic order, which seeks to minimise the makespan under thread constraints and order precedence constraints. The problem is formulated as a Mixed Integer Programming (MIP) model and a novel depth-first heuristic is proposed to solve it. The depth-first heuristic shows high effectiveness and efficiency, compared with the current policy and the genetic algorithm in both small/medium-scale and large-scale cases from the real transaction data. In addition, two extensions on precedence constraint reduction and resource allocation are discussed to further improve and manage the e-order fulfilment process. [ABSTRACT FROM AUTHOR]

Trapped ions (TIs) are at the forefront of quantum computing implementation, offering unparalleled coherence, fidelity, and connectivity. However, the scalability of TI systems is hampered by the limited capacity of individual ion traps, necessitating intricate ion shuttling for advanced computational tasks. The quantum charge-coupled device (QCCD) framework has emerged as a promising solution, facilitating ion mobility for universal quantum computation. Current QCCD architectures predominantly feature a linear topology, which is increasingly recognized as inefficient for complex quantum operations. Anticipating the shift toward more efficacious designs, this article introduces an innovative quantum scheduling strategy optimized for parallel QCCD topologies. Our strategy proposes a probabilistic formula for ion movement, alongside ingenious methods for local layer generation and layer compression, yielding a significant reduction in ion shuttle times. Through simulations, we demonstrate that our strategy not only substantially outstrips the linear model but also exhibits better performance over other parallel strategies that employ greedy algorithms. This is achieved through our nuanced resolution of complexities, such as traffic blocks and trap capacity limitations. The consequent reduction in shuttle operations leads to lower energy consumption and an enhancement in the quantum computer's fidelity, ultimately accelerating program execution times.

With the increasing demand for decentralized systems and the widespread usage of blockchain, low throughput and high latency have become the biggest stumbling blocks in the development of blockchain systems. This problem seriously hinders the expansion of blockchain and its application in production. Most existing smart contract scheduling solutions use static feature analysis to prevent contract conflicts during parallel execution. However, the conflicts between transactions are complex; static feature analysis is not accurate enough. In this paper, we first build the dependency between smart contracts by analyzing the features. After numerous experiments, we propose a conflict model to adjust the relationship between threads and conflict to achieve high throughput and low latency. Based on these works, we propose adaptive parallel scheduling for smart contracts on the blockchain. Our adaptive parallel scheduling can distinguish conflicts between smart contracts and dynamically adjust the execution strategy of smart contracts based on the conflict factors we define. We implement our scheme on ChainMaker, one of the most popular open-source permissioned blockchains, and build experiments to verify our solution. Regarding latency, our solution demonstrates remarkable efficiency compared with the fully parallel scheme, particularly in high-conflict transaction scenarios, where our solution achieves latency levels just one-twentieth of the fully parallel scheme. Regarding throughput, our solution significantly outperforms the fully parallel scheme, achieving 30 times higher throughput in high-conflict transaction scenarios. These results highlight the superior performance and effectiveness of our solution in addressing latency and throughput challenges, particularly in environments with high transaction conflicts.

Parallel hierarchical scheduling of multicore processors in avionics hypervisor is being studied. Parallel hierarchical scheduling utilizes modular reasoning about the temporal behavior of the upper Virtual Machine (VM) by partitioning CPU time. Directed Acyclic Graphs (DAGs) are used for modeling functional dependencies. However, the existing DAG scheduling algorithm wastes resources and is inaccurate. Decreasing the completion time (CT) of DAG and offering a tight and secure boundary makes use of joint-level parallelism and inter-joint dependency, which are two key factors of DAG topology. Firstly, Concurrent Parent and Child Model (CPCM) is researched, which accurately captures the above two factors and can be applied recursively when parsing DAG. Based on CPCM, the paper puts forward a hierarchical scheduling algorithm, which focuses on decreasing the maximum CT of joints. Secondly, the new Response Time Analysis (RTA) algorithm is proposed, which offers a general limit for other execution sequences of Noncritical joints (NC-joints) and a specific limit for a fixed execution sequence. Finally, research results show that the parallel hierarchical scheduling algorithm has higher performance than other algorithms. [ABSTRACT FROM AUTHOR]

In a high‐mix and low‐volume manufacturing facility, heterogeneous jobs introduce frequent reconfiguration of machines which increases the chance of unplanned machine breakdowns. As machines are often nonidentical and their performance degrades over time, it is critical to consider the heterogeneity and non‐stationarity of the machines during scheduling. We propose a reinforcement learning‐based framework with a novel sampling method to train the agent to schedule heterogeneous jobs on non‐stationary unreliable parallel machines to minimize weighted tardiness. The results indicate that the new sampling approach expedites the learning process and the resulting policy significantly outperforms static dispatching rules. [ABSTRACT FROM AUTHOR]

Due to the barrel effect of heterogeneous Spark clusters, unreasonable parallelism leads to poor adaptation of task allocation to the power of workers, which affects cluster computational efficiency and resource utilization. Aiming at this issue, the node resource models are firstly established, the coupling relationships among data distribution, parallelism parameters and task allocation are analyzed, and the optimization objective of the algorithm is proposed. The data skew correction scheduling strategy DSCS for heterogeneous Spark cluster is designed, which includes the parallelism prediction algorithm, data skew correction algorithm and heterogeneous task allocation algorithm. The prediction algorithm sets the parallelism degree in advance, the data skew correction algorithm performs data re-partitioning and parallelism correction according to the statistical information of the first stage, and the heterogeneous task allocation algorithm reasonably allocates the tasks to the workers according to their computing capabilities in the heterogeneous cluster, so as to improve the adaptability of data volume and worker's power and optimize the overall performance of Spark cluster. The experimental results show that the algorithm achieves performance improvement under different job types and dataset conditions, and can effectively reduce the probability of spill to the external storage of workers [ABSTRACT FROM AUTHOR]

Minimizing execution time, energy consumption, and network load through scheduling algorithms is challenging for multi-processor-on-chip (MPSoC) based network-on-chip (NoC) systems. MPSoC based systems are prevalent in high performance computing systems. With the increase in computing capabilities of computing hardware, application requirements have increased many folds, particularly for real world scientific applications. Scheduling large scientific workflows consisting hundreds and thousands of tasks consume significant amount of time and resources. In this article, energy aware parallel scheduling techniques are presented primarily aimed at reducing the algorithm execution time while considering network load. Experimental results reveal that the proposed parallel scheduling algorithms achieve significant reduction in execution time.

Scheduling problems can be alternately approached by methods based on discrete mathematical tools. One obtains a model of a given production technology by representing the relations of the phases of production as partial ordered sets. To solve the scheduling problem in such a case one basically needs a linear order. As an important result of the theory of partial orders we can cite the Szpilrajn theorem, stating that each partial order can be extended to a linear order. Studying the order congruences of partially ordered sets it became clear that the minimal linear order congruences can be successfully applied in investigating scheduling problems. An algorithm for finding minimal linear order congruences is introduced, and a partition of jobs obtained which carries important information about the solution of the parallel scheduling problem. [ABSTRACT FROM AUTHOR]

Parallel hierarchical scheduling of multicore processors in avionics hypervisor is being studied. Parallel hierarchical scheduling utilizes modular reasoning about the temporal behavior of the upper Virtual Machine (VM) by partitioning CPU time. Directed Acyclic Graphs (DAGs) are used for modeling functional dependencies. However, the existing DAG scheduling algorithm wastes resources and is inaccurate. Decreasing the completion time (CT) of DAG and offering a tight and secure boundary makes use of joint-level parallelism and inter-joint dependency, which are two key factors of DAG topology. Firstly, Concurrent Parent and Child Model (CPCM) is researched, which accurately captures the above two factors and can be applied recursively when parsing DAG. Based on CPCM, the paper puts forward a hierarchical scheduling algorithm, which focuses on decreasing the maximum CT of joints. Secondly, the new Response Time Analysis (RTA) algorithm is proposed, which offers a general limit for other execution sequences of Noncritical joints (NC-joints) and a specific limit for a fixed execution sequence. Finally, research results show that the parallel hierarchical scheduling algorithm has higher performance than other algorithms.

In wireless sensor networks (WSNs), spectrum efficiency and energy efficiency are two challenging issues to be addressed due to the scarcity of spectrum and its limited energy. In this paper, we study efficient parallel scheduling with power control and successive interference cancellation (SIC) aimed at maximizing spectrum and energy efficiency, and formulate the efficiency maximization scheduling (EMS) problem as a mixed integer nonlinear programming (MINIP) problem. Given the high complexity caused by mixed variables, we first analyze the critical variables affecting efficiency to transform the MINIP problem into a combinatorial linear programming (LP) problem, which is further decomposed into two linear minimization problems. Then, a recursive relationship between the optimization variables is explored, through which we propose a two-stage scheme that solves the minimization problems with lower complexity. Finally, distributed implementation of the scheduling scheme is provided to iteratively explore the maximum feasible concurrent links in the networks. Extensive results demonstrate the superior performance of our proposed scheme in improving spectrum and energy efficiency. Specifically, our scheme achieves 12.16% to 66.15% higher spectrum efficiency and 18.84% to 88.20% higher energy efficiency than the existing schemes. [ABSTRACT FROM AUTHOR]

Datacenter operations today provide a plethora of new queueing and scheduling problems. The notion of a "job" has become more general and multi-dimensional. The ways in which jobs and servers can interact have grown in complexity, involving parallelism, speedup functions, precedence constraints, and task graphs. The workloads are vastly more variable and more heavy-tailed. Even the performance metrics of interest are broader than in the past, with multi-dimensional service-level objectives in terms of tail probabilities. The purpose of this article is to expose queueing theorists to new models, while providing suggestions for many specific open problems of interest, as well as some insights into their potential solution. [ABSTRACT FROM AUTHOR]

The field-programmable gate array (FPGA)-based real-time simulator takes advantage of many merits of FPGA, such as small time-step, high simulation precision, rich I/O interface resources, and low cost. The sparse linear equations formed by the node conductance matrix need to be solved repeatedly within each time-step, which introduces great challenges to the performance of the real-time simulator. In this paper, a fine-grained solver of the FPGA-based real-time simulator for active distribution networks is designed to meet the computational demand. The framework of the solver, offline process design on PC and online process design on FPGA are proposed in detail. The modified IEEE 33-node system with photovoltaics is simulated on a 4-FPGA-based real-time simulator. Simulation results are compared with PSCAD/EMTDC under the same conditions to validate the solver design.

Modern computational platforms are characterized by the heterogeneity of their processing elements. Additionally, there are many algorithms which can be structured as a set of procedures or tasks with different computational cost. Balancing the computational load among the available processing elements is one of the main keys for the optimal exploitation of such heterogeneous platforms. When the processing time of any procedure executed on any of the available processing elements is known, this workload-balancing problem can be modeled as the well-known scheduling on unrelated parallel machines problem. Solving this type of problems is a big challenge due to the high heterogeneity on both, the tasks and the machines. In this paper, the balancing problem has been formally defined as a global optimization problem which minimizes the makespan (parallel runtime) and a heuristic based on a Genetic Algorithm, called Genetic Scheduler (GenS), has been developed to solve it. In order to analyze the behavior of GenS for several heterogeneous clusters, an example taken from the field of statistical mechanics has been considered as a case study: an active microrheology model. Given this type of problem and a heterogeneous cluster, we seek to minimize the total runtime to extend and analyze in depth the case of study. In such context, a task consists of the simulation of a tracer particle pulled into a cubic box with smaller bath particles. The computational load depends on the total number of the bath particles. Moreover, GenS has been compared to other dynamic and static scheduling approaches. The experimental results of such a comparison show that GenS outperforms the rest of the tested alternatives achieving a better distribution of the computational workload on a heterogeneous cluster. So, the scheduling strategy developed in this paper is of potential interest for any application which requires the execution of many tasks of different duration (a priori known) on a heterogeneous cluster. [ABSTRACT FROM AUTHOR]

This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as P | p j = 1 , in-tree | ∑ C j with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly NP -hard. [ABSTRACT FROM AUTHOR]

To support the large-scale analytic for Web applications, the backend distributed data management system must provide the service for accessing massive data. Thus, the scan operation becomes a critical step. To improve the performance of scan operation, modern data management systems usually rely on the simple partitioned parallelism. Under the partitioned parallelism, tables are consist of several partitions, and each scan operation can access multiple partitions separately. It is a simple and effective solution for a single scan operation. In this paper, we consider managing multiple scan operations together, where the situation is no longer straightforward. To address the problem, we propose the parallel strategy to schedule batched scan operations together beyond the simple partitioned parallelism. For the sake of performance, first, we utilize replications to increase the parallelism and propose an effective load balancing strategy over replication nodes based on linear programming. Second, we propose an effective chunk-based scheduling algorithm for multi-threading parallelism on each node to guarantee all threads have even workloads under a qualified cost model. Finally, we integrate our parallel scan strategy into an open-sourced distributed data management system. Experimental evaluation shows our parallel scan strategy significantly improves the performance of scan operation. [ABSTRACT FROM AUTHOR]

The traditional big data parallel scheduling algorithm has a small number of ships and the scheduling accuracy is very poor. In order to solve this problem, a new ship big data parallel scheduling algorithm based on cloud computing is studied, and the computing framework of the algorithm is constructed. The computing framework includes infrastructure services, software services and platform services. The scheduling process is discussed. The horizontal and vertical coordinates of each ship in the dimensional network are scheduled. A set of energy-aware dual-adaptation dynamic genetic scheduling strategy is constructed. The scheduling strategy is based on the traditional genetic algorithm, and sets the dual optimization targets with weights, which are the execution time of the task and the energy consumption of the infrastructure. By adjusting the optimization weight, the optimization center of gravity can be controlled. The scheduling strategy also fully considers the dynamics of the cloud computing environment and the traditional algorithm. The experimental results show that the cloud computing-based ship big data parallel scheduling algorithm can simultaneously schedule multiple ships, and the scheduling accuracy is very high. The algorithm has broad market development space and is worthy of promotion. [ABSTRACT FROM AUTHOR]

This paper provides a unified family of algorithms with performance guarantees for malleable scheduling problems on flows. A flow represents a set of jobs with precedence constraints. Each job has a speedup function that governs the rate at which work is done on the job as a function of the number of processors allocated to it. In our setting, each speedup function is linear up to some job-specific processor maximum. A key aspect of malleable scheduling is that the number of processors allocated to any job is allowed to vary with time. The overall objective is to minimize either the total cost (minisum) or the maximum cost (minimax) of the flows. Our approach handles a very general class of cost functions, and in particular provides the first constant-factor approximation algorithms for total and maximum weighted completion time. Our motivation for this work was scheduling in MapReduce, and we also provide experimental evaluations that show good practical performance. [ABSTRACT FROM AUTHOR]

This paper is based on the multi-objective optimization problem of mixed shop scheduling problem, the strong coupling of the maximum flow and the minimum time, and the deficiencies of the immune genetic algorithm including high computational complexity and high spatial dimension. This paper establishes a mixed shop scheduling mathematical model with the minimization of the maximum total completion time as the target, and puts forward to use the immune clonal selection algorithm to solve the problem. In the algorithm population construction, it uses the grouping strategy, introduces the cross and delete operator, retains the excellent individuals through memory space, deletes the relatively bad individual, and improves the algorithm's global optimization ability. In order to verify the effectiveness of the proposed algorithm, under the two experimental environments of workpiece machining and automobile shock absorber processing workshop scheduling, simulation experiments are conducted. The experimental results show that the proposed algorithm has better performance, and can achieve smaller maximum total completion time with less iteration. The algorithm can find the global optimal solution of the multi-objective problem, which has a strong practical significance. [ABSTRACT FROM AUTHOR]

In cloud computing, scheduling plays an eminent role while processing enormous jobs. The paralle jobs utmost need parallel processing capabilities which leads to CPU underutilization mainly due to synchronization and communication among parallel processes. Researchers introduced several algorithms for scheduleing parallel jobs namely, Conservative Migration Consolidation supported Backfilling (CMCBF) and Aggressive Migration Consolidation supported Backfilling (AMCBF). The greatest challenge of a existing scheduling algorithm is to improve the data center utilization without affecting job responsiveness. Hence, this work proposes an Effective Multiphase Scheduling Approach (EMSA) to process the jobs. In EMSA, the jobs are initially preprocessed and batched together to avoid starvation and to mitigate unwanted delay. Later, an Associate Priority Method has been proposed which prioritizes the batch jobs to minimize the number of migrations. Finally, the prioritized jobs are scheduled using Priority Scheduling with BackFilling algorithm to utilize the intermediate idle nodes. Moreover, the virtualization technology partitions the computing capacity of the Virtual Machine (VM) into two-tier VM as foreground VM (FVM) and Background VM (BVM) to improve node utilization. Hence, Priority Scheduling with Consolidation based BackFilling algorithm has been deployed in a two-tier VM that processes the jobs by utilizing the VMs effectively. Experimental results show that the performance of the proposed work performs better than other existing algorithms by increasing the resource utilization by 8%. [ABSTRACT FROM AUTHOR]

Polling control system is widely used in production and life including time-sharing computer systems, industrial control, communications, and computer networks. The article proposes a new polling control system based on Busy/Idle queues, which sorts normal polling queues into Busy Queues (BQ) and Idle Queues (IQ) according to if there are customers in the queue. Then, BQ is served by a Gated access policy and IQ keeps a sleeping state until it is woken up by arriving customers. Moreover, parallel scheduling is used to save switch-over time. We build a system model using the embedded Markov chain, probability mother function, the throughput, cycle time, mean queue length and mean waiting time of significant system characteristics. Theoretical calculated values are approximately equal to the simulated values, indicating that the new system is correct and achieves a better performance than the traditional polling scheme. [ABSTRACT FROM AUTHOR]

In recent years, there has been significant interest in developing real-time schedulers for parallel tasks. Most of that research has concentrated on idealized task models where tasks do not access any shared resources protected with locks. In this paper, we consider the problem of scheduling parallel tasks which experience contention due to shared resources. In particular, we provide a schedulability test for federated scheduling by deriving blocking time analyses for parallel tasks that access shared resources protected by FIFO-ordered and priority-ordered spin locks. Our numerical evaluation on randomly generated task sets indicates that priority-ordered locks generally provide better schedulability results than FIFO-ordered locks. We also incorporated both FIFO-ordered and priority-ordered spin lock implementations into a federated scheduling platform, which is able to schedule parallel tasks written with OpenMP. Via empirical evaluations, we found that priority-ordered locks also have better performance than FIFO-ordered locks in practice. [ABSTRACT FROM AUTHOR]

Copyright of Computer Measurement & Control is the property of Magazine Agency of Computer Measurement & Control and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Jobs are executed in a multitasking framework on the premise of processor scheduling, data transfer capacity scheduling. Work scheduling in parallel preparing use diverse sorts of algorithms and systems which are utilized to decrease the quantity of deferred employments. There are distinctive sort of scheduling algorithms and systems used to lessen the execution time of assignments. We can execute our employments utilizing consecutive or parallel occupation scheduling technique. In successive scheduling strategy we can utilize FCFS, SJF, and Priority algorithm to plan our occupations however in the event of parallel scheduling we can utilize bumble bee, hereditary algorithm, subterranean insect province algorithms to determine the issues of parallel employment scheduling. Insect state algorithm can be utilized when the separation amongst asset and employment is inside 14km. be that as it may, if our asset is all the more far from the 14km separation then we can utilize bumble bee algorithms. In our proposed framework we will half and half subterranean insect state and bumble bee algorithm to execute work scheduling as it enhances the speed to 35% to enhance the scheduling. By utilizing this procedure the general throughput and execution of the framework will be enhanced by utilizing this huge technique. [ABSTRACT FROM AUTHOR]

Several task models have been introduced in the literature to describe the intrinsic parallelism of real-time activities, including fork/join, synchronous parallel, DAG-based, etc. Although schedulability tests and resource augmentation bounds have been derived for these task models in the context of multicore systems, they are still too pessimistic to describe the execution flow of parallel tasks characterized by multiple (and nested) conditional statements, where it is hard to decide which execution path to select for modeling the worst-case scenario. To overcome this problem, this paper proposes a task model that integrates control flow information by considering conditional parallel tasks (cp-tasks) represented by DAGs with both precedence and conditional edges. For this task model, a set of meaningful parameters are identified and computed by efficient algorithms and a response-time analysis is presented for different scheduling policies. Experimental results are finally reported to evaluate the efficiency of the proposed schedulability tests and their performance with respect to classic tests based on both conditional and non-conditional existing approaches. [ABSTRACT FROM PUBLISHER]

To provide customized services for concurrent distributed applications in optical networks, a load balanced multi-source multi-path parallel scheduling strategy was proposed, in which the network load and applications load are equally shared in different resources nodes. Simulation results validate that this strategy can effectively reduces the block ratio of distributed services compared with single-source single-path strategy and multi-source multi-path strategy. A testbed of reconfigurable optical network for distributed services is designed to validate the feasibility and effectively of the load balanced parallel scheduling strategy through an example of distributed GridFTP service. The experiment results show,considering the load balance of the application resources and network resources together, this strategy with can successfully decrease the process time of distributed services in grid system and improve system performance.

In order to meet the need of the diversity and complexity of large data requirements and application services, this paper presented using the technology of application virtualization to build an application service layer between the layer of PaaS and IaaS, and building the multicore-aware parallel scheduler in the application service management platform.It proposed a novel multi-granular application management platform to help customers to build new functions by combining the fine-grained application units. Moreover, it used the multicore-aware parallel scheduling model to dispatch application requests to increase the system flexibility and applicability. From the results of the experimental, it shows that the application services can be combined to set up a new function for the business system conveniently, and the parallel scheduler can use the resources effectively by parallel scheduling the applications to improve the throughput of the platform. [ABSTRACT FROM AUTHOR]

This study proposes a novel multi-granular application management platform between PaaS and IaaS layers that uses application virtualization techniques. A multi-core-aware parallel scheduling model is then investigated on the platform. Assisted by fine-grained application units, new functions can be created by combining the application units in different granularities based on business requirements. The multi-core-aware parallel scheduling model was developed to process application requests, and not only increases system flexibility and applicability but also improves fine-grained computing resource allocation, resource utilization of the fundamental infrastructure, and system throughput. [ABSTRACT FROM AUTHOR]

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. In this paper, we consider the global earliest deadline first (GEDF) scheduling policy for task sets consisting of parallel tasks. Each task can be represented by a directed acyclic graph (DAG) where nodes represent computational work and edges represent dependences between nodes. In this model, we prove that GEDF provides a capacity augmentation bound of $$4-\frac{2}{m}$$ and a resource augmentation bound of $$2-\frac{1}{m}$$ . The capacity augmentation bound acts as a linear-time schedulability test since it guarantees that any task set with total utilization of at most $$m/(4-\frac{2}{m})$$ where each task's critical-path length is at most $$1/(4-\frac{2}{m})$$ of its deadline is schedulable on $$m$$ cores under GEDF. In addition, we present a pseudo-polynomial time fixed-point schedulability test for GEDF; this test uses a carry-in work calculation based on the proof for the capacity bound. Finally, we present and evaluate a prototype platform-called PGEDF-for scheduling parallel tasks using global earliest deadline first (GEDF). PGEDF is built by combining the GNU OpenMP runtime system and the $$\text {LITMUS}^\text {RT}$$ operating system. This platform allows programmers to write parallel OpenMP tasks and specify real-time parameters such as deadlines for tasks. We perform two kinds of experiments to evaluate the performance of GEDF for parallel tasks. (1) We run numerical simulations for DAG tasks. (2) We execute randomly generated tasks using PGEDF. Both sets of experiments indicate that GEDF performs surprisingly well and outperforms an existing scheduling techniques that involves task decomposition. [ABSTRACT FROM AUTHOR]

Wavefront parallelism is effective for parallel video encoding thanks to its merits of low latency, no quality loss and high degree of parallelism. In traditional video encoders, macroblock row wavefront (MRW) parallelism was widely adopted. However the performance of MRW is limited by workload unbalance and computing resource unbalance among multiple work threads. This paper proposes a new dynamic macroblock wavefront (DMW) parallelism to alleviate the limitations of MRW. In DMW, the available macroblocks (MBs) are scheduled to work threads MB by MB other than MB row by MB row; and after one MB is encoded by a work thread, the MB on its right (if available) has the highest priority to be scheduled to avoid synchronization delay. Experimental results demonstrate that video encoder with traditional MRW can be accelerated by more than 10% with our proposed DMW. When hyper-threading is used, the advantage of DMW is more prominent. [ABSTRACT FROM AUTHOR]

The COSMIC-2 mission is a follow-on mission of the Constellation Observing System for Meteorology, Ionosphere, and Climate (COSMIC) with an upgraded payload for improved radio occultation (RO) applications. The objective of this paper is to develop a near-real-time (NRT) orbit determination system, called NRT National Chiao Tung University (NCTU) system, to support COSMIC-2 in atmospheric applications and verify the orbit product of COSMIC. The system is capable of automatic determinations of the NRT GPS clocks and LEO orbit and clock. To assess the NRT (NCTU) system, we use eight days of COSMIC data (March 24-31, 2011), which contain a total of 331 GPS observation sessions and 12 393 RO observable files. The parallel scheduling for independent GPS and LEO estimations and automatic time matching improves the computational efficiency by 64% compared to the sequential scheduling. Orbit difference analyses suggest a 10-cm accuracy for the COSMIC orbits from the NRT (NCTU) system, and it is consistent as the NRT University Corporation for Atmospheric Research (URCA) system. The mean velocity accuracy from the NRT orbits of COSMIC is 0.168 mm/s, corresponding to an error of about 0.051 μrad in the bending angle. The rms differences in the NRT COSMIC clock and in GPS clocks between the NRT (NCTU) and the postprocessing products are 3.742 and 1.427 ns. The GPS clocks determined from a partial ground GPS network [from NRT (NCTU)] and a full one [from NRT (UCAR)] result in mean rms frequency stabilities of 6.1E-12 and 2.7E-12, respectively, corresponding to range fluctuations of 5.5 and 2.4 cm and bending angle errors of 3.75 and 1.66 μrad . [ABSTRACT FROM PUBLISHER]

Optical interconnects are considered as a very appealing solution for future high speed interconnections in core networks and parallel computers. In this paper, we study multicast scheduling in all-optical packet interconnects/switches. We first propose a novel optical buffer called multicast-enabled fiber-delay-lines (M-FDLs), which can provide flexible delay for copies of multicast packets using only a small number of FDL segments. We then present a Low Latency Multicast Scheduling (LLMS) Algorithm that considers the schedule of each arriving packet for multiple time slots. We show that LLMS has several desirable features, such as a guaranteed delay upper bound and adaptivity to transmission requirements. To relax the time constraint of LLMS, we further propose a pipeline and parallel architecture for LLMS that distributes the scheduling task to multiple pipelined processing stages, with N processing modules in each stage, where N is the size of the interconnect. Finally, by implementing it with simple combination circuits, we show that each processing module can complete the packet scheduling for a time slot in O(1) time. The performance of LLMS is evaluated extensively against statistical traffic models and real Internet traffic traces, and the results show that the proposed LLMS algorithm can achieve superior performance in terms of average packet delay and packet drop ratio. [ABSTRACT FROM PUBLISHER]

A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry (PG) based balanced bipartite graphs. Many of these applications of finite projective geometry are actively being researched upon, especially in coding theory. Almost all these applications need large bipartite graphs, whose nodes represent parallel computations. To reduce its implementation cost, reducing amount of system/hardware resources during design is an important engineering objective. In this context, we present a scheme to reduce resource utilization while designing systems modeled using PG-based graphs. In such systems, the number of processing units is equal to the number of vertices, each performing an atomic computation. We present a novel way of partitioning the vertex set assigned to various atomic computations, into blocks. Each block of partition is then assigned to a processing unit. A processing unit performs the computations corresponding to the vertices in the block assigned to it in a sequential fashion, thus creating the effect of folding the overall computation. The symmetric properties of projective space lattices enable us to develop a conflict-free communication schedule. We employed the technique of coset decomposition of a finite field for partitioning. The folding scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. We first provide a scheme for a finite projective space of dimension five, and the corresponding schedules. This specific scheme is then generalized for arbitrary finite projective spaces. Both the folding schemes have been verified by both simulation as well as hardware prototyping. For example, a semi-parallel decoder architecture for a new class of expander codes was designed and implemented using this scheme, with potential deployment in DVD-R/CD-ROM drives. [ABSTRACT FROM AUTHOR]

Due to the nature of a dynamic group of picture (GOP) structure, parallel scheduling for video encoding becomes challenging. To address this, the balanced frame-level parallel scheduling algorithms are developed. The proposed approaches first determine the frame priority and then the thread priority assignment for scheduling. The concept of the algorithms lies in the analysis of coding complexity, temporal influence, and the required temporal burden to finish coding. To complete the scheduling with the dynamic GOP structure, a block-based abrupt and gradual scene change detection algorithm is also proposed to determine the GOP structure adaptively. The experiments show that the scheduling performance is close to the optimal. In addition, the concept of batch processing is incorporated so that the required buffer can be reduced. [ABSTRACT FROM PUBLISHER]

A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry (PG)-based balanced bipartite graphs. Many of these applications of finite projective geometry are actively being researched upon, especially in coding theory. Almost all these applications need large bipartite graphs, whose nodes represent parallel computations. To reduce its implementation cost, reducing amount of system/hardware resources during design is an important engineering objective. In this context, we present a scheme to reduce resource utilization while designing systems modeled using PG-based graphs. In such systems, the number of processing units is equal to the number of vertices, each performing an atomic computation. We present a novel way of partitioning the vertex set assigned to various atomic computations, into blocks. Each block of partition is then assigned to a processing unit. A processing unit performs the computations corresponding to the vertices in the block assigned to it in a sequential fashion, thus creating the effect of folding the overall computation. The symmetric properties of projective space lattices enable us to develop a conflict-free communication schedule. We employed the technique of coset decomposition of a finite field for partitioning. The folding scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. We first provide a scheme for a finite projective space of dimension five, and the corresponding schedules. This specific scheme is then generalized for arbitrary finite projective spaces. Both the folding schemes have been verified by both simulation as well as hardware prototyping. For example, a semi-parallel decoder architecture for a new class of expander codes was designed and implemented using this scheme, with potential deployment in DVD-R/CD-ROM drives. [ABSTRACT FROM AUTHOR]

Abstract: Previous researches proposed a dynamic supply chain model, which consists of three model components; those are clients, manufacturers, and suppliers. The model provided a numerical method to determine suitable prices and delivery times of products through the iteration of both the modification processes of production schedules and the negotiation processes among the model components. This paper proposes an effective order selection method for suppliers to find a suitable order in a number of orders sent from the lower-layer organizations. Computational experiments were carried to evaluate the effectiveness of the proposed method by using a developed supply chain simulation system. [Copyright &y& Elsevier]

Abstract: Data backup can realize quick data recovery in case of system crash. With the popularity of Software as a service (Saas), online backup service has becoming a hot topic within cloud storage. How to establish efficient connection between massive users and storage nodes, so as to achieve systematical load-balance, to obtain high utilization of network and storage is a crucial problem. This paper proposed two scheduling strategies from the aspects of scheduling by job and object respectively, one is real-time scheduling and the other is long-run scheduling. Experimental analysis demonstrated that long-run scheduling can improve the whole performance of online backup service greatly. [Copyright &y& Elsevier]

Load balancing algorithms are designed essentially to equally distribute the load on processors and maximize their utilities while minimizing the total task execution time. In order to achieve these goals, the load-balancing mechanism should be 'fair' in distributing the load across the different processors. This implies that the difference between the heaviest-loaded and the lightest-loaded processors should be minimized. Therefore, the load information on each processor must be updated such that the load-balancing mechanism can be more effective. In this work, we present an application independent dynamic algorithm for scheduling tasks and load- balancing in message passing systems. We propose a DAG-based Dynamic Load Balancing algorithm for Real time applications (DAG-DLBR) that is designed to work dynamically to cope with possible changes in the load that might occur during runtime. This algorithm addresses the challenge of devising a load balancing scheme which judicially deals with the hybrid execution of existing real-time application (represented by a Direct Acyclic Graph (DAG)) together with newly arriving jobs. The main objective of this algorithm is to reduce response times of the newly arriving jobs while maintaining the time constrains of the existing DAG. To evaluate the performance of the DAG-DLBR algorithm, a comparison with the performance of two common dynamic load balancing algorithms is presented. This comparison is performed by evaluating, experimentally, the execution time of different load balancing algorithms on a homogenous real parallel machine. In addition, the values of load imbalance, the execution time, and the communication overhead time are evaluated analytically using different benchmarks as test-bed workloads. These workloads cover a wide range of dynamic applications with different task types. Experimental results illustrate the improved performance of the DAG-DLBR algorithm compared to both distributed and hierarchal based algorithms by at least 12 and 19%, respectively. This improvement is true for all workloads, even with highly dependent workload. The DAG-DLBR algorithm achieves lower computation time than its corresponding values of both the distributed and the hierarchical-based algorithms for 4, 8, 12 and 16 processors. [ABSTRACT FROM AUTHOR]

The Chained-Cubic Tree (CCT) interconnection network topology was recently proposed as a continuation for the extended efforts in the area of interconnection networks’ performance improvement. This topology, which promises to exhibit the best properties of the hypercube and tree topologies, needs to be deeply investigated in order to evaluate its performance among other interconnection networks’ topologies. This work comes as a complementary effort, in which the load balancing technique is investigated as one of the most important aspects of performance improvement. This paper proposes a new load balancing algorithm on CCT interconnection networks. The proposed algorithm, which is called Hybrid Dynamic Parallel Scheduling Algorithm (HD-PSA), is a combination of two common load balancing strategies; dynamic load balancing and parallel scheduling. The performance of the proposed algorithm is evaluated both, analytically and experimentally, in terms of various performance metrics; including, execution time, load balancing accuracy, communication cost, number of tasks hops, and tasks locality. [ABSTRACT FROM AUTHOR]

The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms, Algorithmica 37(4):295–326, ) which formulates a wide class of greedy algorithms. For an arbitrary set $\mathbb{S}$ of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of $\mathbb{S}$ . In the case where the jobs are all intervals, we characterize such sets $\mathbb{S}$ and give an efficient algorithm (when $\mathbb{S}$ is finite) for determining this. We show that in general, however, the problem is NP-hard. [ABSTRACT FROM AUTHOR]

To enhance the capacity of wireless mesh networks, a key technique is widely investigated which is the usage of multi-radio and multi-channel diversity. In this paper, a new parallel scheduling system is proposed which exploits MAC diversities by transmitting packets on the radios opportunistically. Compared with conventional packet transmission which follows “one flow one radio”, the new system uses radio diversity to transmit the packets on different radios simultaneously. Two kernel components of this system are selection module and schedule module. A localized selecting algorithm is implemented in the selection model to choose the right radios based on the quality of wireless links; two distributed packet-scheduling algorithms are optional with the schedule component. Finally, a routing metric adapting this system is presented. We have carried out a comprehensive performance evaluation of this system using ns-2. Simulation results show that it can successfully harness diversity of multi-radio and multi-channel to provide considerable improvements over a baseline multi-channel system in several situations. [ABSTRACT FROM AUTHOR]

In this paper we present an efficient algorithm for compile-time scheduling and clustering of parallel programs onto parallel processing systems with distributed memory, which is called The Dynamic Critical Path Scheduling DCPS. The DCPS is superior to several other algorithms from the literature in terms of computational complexity, processors consumption and solution quality. DCPS has a time complexity of O(e + v log v), as opposed to DSC algorithm O((e+v) log v) which is the best known algorithm. Experimental results demonstrate the superiority of DCPS over the DSC algorithm. [ABSTRACT FROM AUTHOR]

Li, X., and Guo, J.-J., 2019. Research on ship data big data parallel scheduling algorithm based on cloud computing. In: Gong, D.; Zhu, H., and Liu, R. (eds.), Selected Topics in Coastal Research: Engineering, Industry, Economy, and Sustainable Development. Journal of Coastal Research, Special Issue No. 94, pp. 535–539. Coconut Creek (Florida), ISSN 0749-0208. The traditional big data parallel scheduling algorithm has a small number of ships and the scheduling accuracy is very poor. In order to solve this problem, a new ship big data parallel scheduling algorithm based on cloud computing is studied, and the computing framework of the algorithm is constructed. The computing framework includes infrastructure services, software services and platform services. The scheduling process is discussed. The horizontal and vertical coordinates of each ship in the dimensional network are scheduled. A set of energy-aware dual-adaptation dynamic genetic scheduling strategy is constructed. The scheduling strategy is based on the traditional genetic algorithm, and sets the dual optimization targets with weights, which are the execution time of the task and the energy consumption of the infrastructure. By adjusting the optimization weight, the optimization center of gravity can be controlled. The scheduling strategy also fully considers the dynamics of the cloud computing environment and the traditional algorithm. The experimental results show that the cloud computing-based ship big data parallel scheduling algorithm can simultaneously schedule multiple ships, and the scheduling accuracy is very high. The algorithm has broad market development space and is worthy of promotion. [ABSTRACT FROM AUTHOR]