Arbitrary Processor Network Scheduling Algorithms in Parallel Computing

Shobhit Gupta,Ranjit Rajak,Girish Kumar Singh,Sanjay Jain 한국산학기술학회 2015 SmartCR Vol.5 No.3

Task scheduling in parallel computing is represented by a directed acyclic graph, and it is called multiprocessor task scheduling. The primary objective of task scheduling algorithm is to minimize the total execution time i.e. scheduling length. There are various types of task scheduling algorithms: Bound Number of Processor Scheduling, and Arbitrary Processor Network Scheduling Algorithms. Bound Number of Processor Scheduling algorithms are used for limited number of processors; since it does not use task duplication, link contention, and routing strategy for communication. But Arbitrary Processor Network scheduling algorithms are considered for link contention routing strategy in communication. It uses arbitrary network topology. In this paper, we have studied different Arbitrary Processor Network scheduling algorithms: Mapping Heuristic, Dynamic Level Scheduling, Bottom Up, and Bubble Scheduling and Allocation. The primary objective of this survey paper is to explain various Arbitrary Processor Network scheduling algorithms and their functionality, priority attributes, and time complexity. The performance metrics can also be used for comparison of different Arbitrary Processor Network scheduling algorithms.

Static Task Scheduling Algorithm with Minimum Distance for Multiprocessor System (STMD)

Ranjit Rajak,C.P.Katti 한국산학기술학회 2015 SmartCR Vol.5 No.2

Task scheduling in the multiprocessor environment is considered to be a NP-complete problem. It is also called a multiprocessor scheduling. Here, a parallel program is divided into a number of subtasks and it is mapped on the processors for concurrent execution. The objective of task scheduling is to reduce scheduling length of a given application program. Considering that task scheduling is represented by Directed Acyclic Grape (DAG). There are two types of task scheduling algorithms: static task scheduling and dynamic task scheduling algorithms. In this paper, we propose a new task scheduling algorithm based on minimum distance and an entry task duplicated on the processors. The minimum distance computes between an entry task and its successors. It includes, minimum distance of parent task, execution time and communication time Here , also considering a priority list (PL) attribute that contains tasks information of a given application program whose distance is minimum from an entry task. Finally, we will do comparative study of the proposed algorithm with Bounded Number of Processors (BNP) class of scheduling algorithms. It has done based on the following matrices: Scheduling Length, Speedup, Efficiency, Load Balancing and Normalized Scheduling Length (NSL). It showed proposed algorithm gives better result than BNP class of scheduling algorithms.

Research on the Scheduling of Legal Operating Vehicles based on NFC

Jiyan Lin,Peini Shang,Fei Yang,Yongheng Zhang 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.11

In the study of reasons that cause the flush illegal operating vehicles, we found out that the insufficient legal operating vehicles were the main cause. In order to efficiently solve the illegal operating, the paper brings out the research of scheduling algorithm about the legal operating vehicles based on NFC. The research uses the NFC technology to realize the intelligent and fast identification and the scheduling algorithm to realize the problem of insufficient legal operating vehicles. The scheduling can be divided into two stages--the multi-level queues high response ratio first scheduling and the multi-level queues earliest available time first scheduling. The algorithm can choose the user whose response ratio is the highest from the users’scheduling list and allocate the user who has the highest ratio to the legal operating vehicle who has the earliest available time that in the same area. Experiment indicates that the scheduling success ratio, throughput, average waiting time of the scheduling algorithm are superior to random travel of the drivers and can efficiently resolve the insufficient of legal operating vehicles.

광 버스트 스위칭 네트워크의 코어 노드를 위한 그룹 스케줄링 성능 분석

신종덕,이재명,김형석 한국통신학회 2004 韓國通信學會論文誌 Vol.29 No.8B

본 논문에서는 광 버스트 스위칭 네트워크의 코어 노드에 그룹 스케줄링 알고리즘을 적용하여, 전산 모의실험을 통해 그 성능을 측정하였다. 성능 평가를 위해, 다채널 입출력 포트를 갖는 코어 노드에 대하여, 즉시 스케줄링 방식과 비교하였다. 그룹 스케줄링은 노드에 먼저 도착하는 버스트 헤더 패킷의 정보를 이용하여 일정한 시간 창에 스케줄링 될 버스트들을 스케줄링하기 때문에, 전산 모의실험 결과 그룹 스케줄링 방식이 즉시 스케줄링 방식보다 버스트 손실 확률과 채널 이용률이 모두 개선되었으며 부하의 증가에 따라 차이가 더욱 커졌다. 또한, 출력포트에 파장 변환기를 사용한 경우에 대해서도 성능을 측정하였다. 이 경우에는, 그룹 스케줄링 방식과 즉시 스케줄링 방식의 버스트 손실 확률과 채널 이용률 모두 부하 범위 0.1-0.9에서 서로 비슷하게 나타났으나. 파장 변환기의 사용 빈도는 즉시 스케줄링이 그룹 스케줄링보다 약 7배 이상으로 높아, 그룹 스케줄링 방식을 사용하면 보다 경제적인 노드 구조를 구현할 수 있음을 알 수 있었다. In this paper, we applied a group scheduling algorithm to core nodes in an optical burst switching (OBS) network and measured its performance by simulation. For the case of core nodes with multi-channel input/output ports, performance of the group scheduling has been compared to that of the immediate scheduling. Since the group scheduling has a characteristic of scheduling a group of bursts simultaneously in a time window using information collected from corresponding burst header packets arrived earlier to a core node, simulation results show that the group scheduling outperforms the immediate scheduling in terms of both burst loss probability and channel utilization and the difference gets larger as the load increases. Another node configuration in which wavelength converters are equipped at the output ports has also been considered. In this case, even though both performance metrics of the group scheduling are almost the same as those of the immediate scheduling in the offered load range between 0.1 and 0.9, the group scheduling has lower wavelength conversion rate than the immediate scheduling by at least a factor of seven. This fact leads us to the conclusion that the group scheduling makes it possible to implement more economical OBS core nodes.

건설프로젝트 공정관리 분야의 최근 연구동향

정순오 경복대학 2002 京福論叢 Vol.6 No.-

본 인구는 문헌조사를 통하여 건설 프로젝트의 공정관리에 관한 국내 및 국외의 최근의 연구동향을 살펴보고 국내 공정관리 분야의 발전방향을 제시하는데 그 목적이 있다. 복잡하고 다양한 건설 프로젝트에서 가장 중요한 것 중의 하나는 적절한 공정관리이며, 건설 공정관리분야의 최근의 연구주제는 최적 공정계획, 비용-공정 통합, 공정관리 기법, 공정지연, 반복작업 공정과 린 건설 등이다. 문헌조사를 통하여 살펴본 결과, 최근에 국내에서는 통합된 공정 및 비용관리, 공기지연 및 클레임에 관한 연구가 증가하고 있으며, 외국에서는 선형 공정기법과 모델이 반복적인 작업의 공정관리를 위해 개발되고 있고, 국내와 마가지로 일정과 비용의 통합에 관한 연구가 많이 진행되고 있다. 본 연구를 통해 얻은 결과로 국내의 건설공정관리 분야의 발전을 위한 방안을 다음과 같이 제시하고자 한다. 첫째로, 과학적이고 실질적인 공정관리를 위한 전문인력 양성 및 교육이 필요하고 지속적인 관리가 요구된다. 둘째로, 국내 건설환경에 맞는 공정관리 기법 개발이 필요하고 계약서나 시방서에 공정관리에 관한 세부사항을 명문화 한다. 마지막으로, 국제기준에 맞는 계약서의 정비 및 공정관리 운영으로 국내외 건설현장에서 증가하는 클레임에 대비하여야 한다. This study attempts to examine recent research trends on the scheduling in construction projects with the investigation of related documents in inland and overseas and offer directions to improve the scheduling in inland. One of the most important factors in complex and diverse construction processes is a proper scheduling. And recent research subjects are optimal scheduling, cost-schedule integration, Scheduling technique, activity delay, repetitive work activity and lean construction, etc. As a result of the document research, it is turned out to be recently increasing to study inregrated schedule and cost control management, and schedule delay and delay claims domestically. On the other hand in overseas, it is being developed linear scheduling techniques and models for the repetitive work scheduling and also making quite a progress in studying integrated schedule and cost control management like here in Korea. The result of this study may offer some suggestions to improve the construction scheduling in Korea as follows. First, it is necessary to train and educate experts for the scientific and substantial scheduling and it is required to maintain it continuously. Second, it is necessary to develop scheduling techniques suitable for. the internal construction environments and stipulate details on the scheduling in contract papers and specifications. Finally, it is necessary to revise contracts and scheduling corresponding with the international standard in order to prepare for increasing claims in construction sites of the country and overseas.

Scheduling Jobs on Cloud Computing using Firefly Algorithm

Demyana Izzat Esa,Adil Yousif 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.7

Cloud computing is a new technology, instead of all computer hardware and software that used on desktop, or somewhere within company's network, it's presented as a service by cloud service providers and accessed via the Internet. Exactly where hardware and software are located and how everything works does not matter. In cloud computing there are many jobs that requires to be executed on the available resources to achieve best minimal execution time. Several optimization methods are available for cloud job scheduling. However, the job scheduling process is still need to be optimized. This paper proposes a new job scheduling mechanism using Firefly Algorithm to minimize the execution time of jobs. The proposed mechanism based on information of jobs and resources such as length of job speed of resource and identifiers. The scheduling function in the proposed job scheduling mechanism firstly creates a set of jobs and resources to generate the population by assigning the jobs to resources randomly and evaluates the population using a fitness value which represents the execution time of jobs. Secondly the function used iterations to regenerate populations based on firefly behavior to produce the best job schedule that gives the minimum execution time of jobs. Several scenarios are implemented using Java Language and CloudSim simulator. Different settings have been considered in the evaluation and experimentation phase to examine the proposed mechanism in different workloads. The first phase of the evaluation process describes how the proposed mechanism can be used to minimize the execution time of jobs. The second phase of the evaluation process compares the proposed mechanism with First Come First Serves (FCFS) algorithm. The results revealed that the proposed mechanism minimizes the execution time significantly. Furthermore, the proposed mechanism outperformed the FCFS algorithm.

SCHEDULE CONSTRUCTION UNDER PRECEDENCE CONSTRAINTS IN FLEXRAY IN-VEHICLE NETWORKS

Armaghan Darbandi,윤석훈,김명균 한국자동차공학회 2017 International journal of automotive technology Vol.18 No.4

As embedded time-triggered applications have widely replaced mechanical systems in modern automobiles, holistic scheduling of tasks and messages of such applications on in-vehicle networks has become a critical issue. For offering QoS (Quality of Service) guarantees, the holistic schedule must satisfy numerous constraints such as protocol specifications, delay constraints and precedence constraints between tasks schedules and messages transmissions. Existing approaches to this problem search through a vast design space of all possible joint task and message schedules. This leads to a high complexity and limits the scalability of such approaches for scheduling the large scale systems. To cope with this problem, we propose an approach that divides the holistic scheduling problem to two sub-problems: the sub-problem of message scheduling and the sub-problem of task scheduling, while precedence relations and end-to-end information passing between task instances and messages are preserved and the end-to-end deadlines are guaranteed. This helps to reduce the workload on the problem solvers and improves efficiency and scalability. In the first sub-problem, our approach optimizes scheduling the set of messages and allocates time windows for scheduling each task with respect to precedence constraints, end-to-end deadlines and FlexRay protocol specifications. The length of each time window helps to preserve the respective tasks schedulability and to provide flexibility for both task and message scheduling. The objective is defined with respect to extensibility issues. In the second sub-problem, our approach optimizes schedule of the set of tasks with respect to their allocated time windows and timing constraints. The objective is defined with respect to latency issues. We optimize the solution to each sub-problem using Mixed Integer Linear Programming optimization framework. Performance evaluations show that, compared with existing holistic scheduling approaches, our approach is more scalable and obtains better solutions in a reasonable amount of time.

Locomotive Scheduling Using Constraint Satisfaction Problems Programming Technique

Hwang, Jong-Gyu,Lee, Jong-Woo,Park, Yong-Jin The Korean Institute of Electrical Engineers 2004 KIEE International Transactions on Electrical Mach Vol.b4 No.1

Locomotive scheduling in railway systems experiences many difficulties because of the complex interrelations among resources, knowledge and various constraints. Artificial intelligence technology has been applied to solve these scheduling problems. These technologies have proved to be efficient in representing knowledge and rules for complex scheduling problems. In this paper, we have applied the CSP (Constraints Satisfaction Problems) programming technique, one of the AI techniques, to solve the problems associated with locomotive scheduling. This method is more effective at solving complex scheduling problems than available mathematical programming techniques. The advanced locomotive scheduling system using the CSP programming technique is realized based on the actual timetable of the Saemaul type train on the Kyong-bu line. In this paper, an overview of the CSP programming technique is described, the modeling of domain and constraints is represented and the experimental results are compared with the real-world existing schedule. It is verified that the scheduling results by CSP programming are superior to existing scheduling performed by human experts. The executing time for locomotive scheduling is remarkably reduced to within several decade seconds, something requiring several days in the case of locomotive scheduling by human experts.

Model Predictive Sensor Scheduling

Eriko Iwasa,Kenko Uchida 제어로봇시스템학회 2008 제어로봇시스템학회 국제학술대회 논문집 Vol.2008 No.10

The sensor scheduling is to select a sensor (or a group of sensors) from multiple sensors at each time step so as to perform optimally a task based on the sensed data. In this paper, we pose a model predictive type deterministic/ stochastic sensor scheduling problem for discrete-time linear Gaussian time-varying systems, and develop an approach to solve these problems based on the dynamic programming recursion. We show first that, in a special case of deterministic scheduling where the Riccati recursion of error covariance satisfies a specific structural condition, the online optimization using the dynamic programming is reduced to a static optimization, so that the model predictive sensor scheduling can be easily implemented online. Next, we discuss the stochastic scheduling problem, and show an alternative condition of optimization reduction, which lead to a stochastic sensor scheduling easily implemented online. Finally, we propose two practical sensor schedulings for deterministic and stochastic case, and discuss an example to illustrate the two sensor schedulings.

실시간 시스템에서 성능 향상 기법

김명준(Myung Jun Kim) 한국IT서비스학회 2017 한국IT서비스학회지 Vol.16 No.3

The real time scheduling is a key research area in high performance computing and has been a source of challenging problems. A periodic task is an infinite sequence of task instance where each job of a task comes in a regular period. The RMS (Rate Monotonic Scheduling) algorithm has the advantage of a strong theoretical foundation and holds out the promise of reducing the need for exhaustive testing of the scheduling. Many real-time systems built in the past based their scheduling on the Cyclic Executive Model because it produces predictable schedules which facilitate exhaustive testing. In this work we propose hybrid scheduling method which combines features of both of these scheduling algorithms. The original rate monotonic scheduling algorithm didn t consider the uniform sampling tasks in the real time systems. We have enumerated some issues when the RMS is applied to our hybrid scheduling method. We found the scheduling bound for the hard real-time systems which include the uniform sampling tasks. The suggested hybrid scheduling algorithm turns out to have some advantages from the point of view of the real time system designer, and is particularly useful in the context of large critical systems. Our algorithm can be useful for real time system designer who must guarantee the hard real time tasks.