2003
Conference article
Restricted
Hybrid Parallelization of a Compact Genetic Algorithm
Hidalgo Ji, Prieto M, Lanchares J, Baraglia R, Tirado F, Garnica O
Genetic Algorithms (GAs) are stochastic optimization heuristics in which searches in solution space are carried out by imitating the population genetics stated in Darwin's theory of evolution. We have focused this work on compact Genetic Algorithms (cGAs), which unlike standard GAs do not manage a population of solutions but only mimics its existence. In this paper we have studied several approaches that can be used to implement parallel cGAs in order to reduce the execution times and to improve the quality of the solutions reached by increasing population sizes. The parallelization models adopted to implement GAs can be classified as: centralized, global, fine grained and coarse grained. For a cGA only the two first models can be applied. Our approach consists in an hybrid model which combines both centralized and global implementations. The cGA incorporates a local search method and has been applied for solving a graph-partitioning problem for solving the Multi-FPGA systems partitioning and placement.DOI: 10.1109/empdp.2003.1183624
Metrics:
Hidalgo Ji, Prieto M, Lanchares J, Baraglia R, Tirado F, Garnica O
Genetic Algorithms (GAs) are stochastic optimization heuristics in which searches in solution space are carried out by imitating the population genetics stated in Darwin's theory of evolution. We have focused this work on compact Genetic Algorithms (cGAs), which unlike standard GAs do not manage a population of solutions but only mimics its existence. In this paper we have studied several approaches that can be used to implement parallel cGAs in order to reduce the execution times and to improve the quality of the solutions reached by increasing population sizes. The parallelization models adopted to implement GAs can be classified as: centralized, global, fine grained and coarse grained. For a cGA only the two first models can be applied. Our approach consists in an hybrid model which combines both centralized and global implementations. The cGA incorporates a local search method and has been applied for solving a graph-partitioning problem for solving the Multi-FPGA systems partitioning and placement.DOI: 10.1109/empdp.2003.1183624
Metrics:
See at:
doi.org 
| CNR IRIS | CNR IRIS | link.springer.com
2002
Conference article
Restricted
SUGGEST: a Web usage mining system
Baraglia R, Palmerini P
During their navigation web users leave many records of their activity. This huge amount of data can be a useful source of knowledge. Sophisticated mining processes are needed for this knowledge to be extracted, understood and used. In this paper we propose aWeb UsageMining (WUM) system, called SUGGEST , designed to efficiently integrate the WUM process with the ordinary web server functionalities. It can provide useful information to make easier the web user navigation and to optimize the web server performance. Two quantities are introduced in order to give a measure of the quality of our WUM system.
Baraglia R, Palmerini P
During their navigation web users leave many records of their activity. This huge amount of data can be a useful source of knowledge. Sophisticated mining processes are needed for this knowledge to be extracted, understood and used. In this paper we propose aWeb UsageMining (WUM) system, called SUGGEST , designed to efficiently integrate the WUM process with the ordinary web server functionalities. It can provide useful information to make easier the web user navigation and to optimize the web server performance. Two quantities are introduced in order to give a measure of the quality of our WUM system.
2007
Conference article
Restricted
Local search for Grid scheduling
Klusacek D, Matyska L, Rudova H, Baraglia R, Capannini G
This work introduces local search based algorithms as a new technique for the Grid scheduling problem. Specific algorithms based on dispatching rules and local search were proposed and implemented to generate schedule for dynamically arriving jobs. Algorithm performance was compared with typical queue-based algorithms from the point of view of objective function optimisation and time required to generate scheduling solutions. Grid environment was simulated by Alea Simulator which is based on modified and extended Grid- Sim toolkit. The results showed that local search based algorithms may be promising technique with better performance than queue-based approaches while still fast enough to provide solution in a reasonable time.
Klusacek D, Matyska L, Rudova H, Baraglia R, Capannini G
This work introduces local search based algorithms as a new technique for the Grid scheduling problem. Specific algorithms based on dispatching rules and local search were proposed and implemented to generate schedule for dynamically arriving jobs. Algorithm performance was compared with typical queue-based algorithms from the point of view of objective function optimisation and time required to generate scheduling solutions. Grid environment was simulated by Alea Simulator which is based on modified and extended Grid- Sim toolkit. The results showed that local search based algorithms may be promising technique with better performance than queue-based approaches while still fast enough to provide solution in a reasonable time.
See at:
abotea.rsise.anu.edu.au | CNR IRIS | CNR IRIS
2008
Conference article
Restricted
VoRaQue: RAnge QUeries on voronoi overlays
Albano M, Ricci L, Baldanzi M, Baraglia R
This paper presents VoRaQue, a software layer supporting range queries on Voronoi P2P overlays. VoRaQue maps data in a 2-dimensional space. The P2P overlay is defined by links connecting nodes that are close in the 2-dimensional space and by a set of long-range links which guarantee a poly-logarithmic routing. When a query is submitted, VoRaQue finds out a node belonging to the region defined by the query. A multicast spanning tree covering that region is then built by applying compass routing, a distributed protocol to embed a spanning tree into a Delaunay Triangulation. The paper presents the basic VoRaQue protocol, then introduces a set of optimizations and finally presents some experimental results.Source: PROCEEDINGS - IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS, pp. 495-500. Marrakech, Morocco, 6-9 Luglio 2008
DOI: 10.1109/iscc.2008.4625648
Metrics:
Albano M, Ricci L, Baldanzi M, Baraglia R
This paper presents VoRaQue, a software layer supporting range queries on Voronoi P2P overlays. VoRaQue maps data in a 2-dimensional space. The P2P overlay is defined by links connecting nodes that are close in the 2-dimensional space and by a set of long-range links which guarantee a poly-logarithmic routing. When a query is submitted, VoRaQue finds out a node belonging to the region defined by the query. A multicast spanning tree covering that region is then built by applying compass routing, a distributed protocol to embed a spanning tree into a Delaunay Triangulation. The paper presents the basic VoRaQue protocol, then introduces a set of optimizations and finally presents some experimental results.Source: PROCEEDINGS - IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS, pp. 495-500. Marrakech, Morocco, 6-9 Luglio 2008
DOI: 10.1109/iscc.2008.4625648
Metrics:
See at:
doi.org | CNR IRIS | ieeexplore.ieee.org | CNR IRIS
2008
Contribution to book
Open Access
Comparison of multi criteria scheduling techniques
Baraglia R, Pasquali M, Capannini G, Klusàcek D, Rudova H
This paper proposes a novel schedule-based approach for scheduling a continuous stream of batch jobs on the machines of a computational Grid. Our new solutions represented by dispatching rule Earliest Gap| Earliest Deadline First (EG-EDF) and Tabu search are based on the idea of ̄lling gaps in the existing schedule. EG-EDF rule is able to build the schedule for all jobs incrementally by applying technique which ̄lls earliest existing gaps in the schedule with newly arriving jobs. If no gap for a coming job is available EG-EDF rule uses Earliest Deadline First (EDF) strategy for including new job into the existing schedule. Such schedule is then optimized using the Tabu search algorithm mov- ing jobs into earliest gaps again. Scheduling choices are taken to meet the Quality of Service (QoS) requested by the submitted jobs, and to optimize the usage of hardware resources. We compared the proposed solution with some of the most common queue-based scheduling algo- rithms like FCFS, EASY back ̄lling, and Flexible back ̄lling. Experi- ments shows that EG-EDF rule is able to compute good assignments, often with shorter algorithm runtime w.r.t. the other queue-based al- gorithms. Further Tabu search optimization results in higher QoS and machine usage while keeping the algorithm runtime reasonable.DOI: 10.1007/978-0-387-09457-1_15
Metrics:
Baraglia R, Pasquali M, Capannini G, Klusàcek D, Rudova H
This paper proposes a novel schedule-based approach for scheduling a continuous stream of batch jobs on the machines of a computational Grid. Our new solutions represented by dispatching rule Earliest Gap| Earliest Deadline First (EG-EDF) and Tabu search are based on the idea of ̄lling gaps in the existing schedule. EG-EDF rule is able to build the schedule for all jobs incrementally by applying technique which ̄lls earliest existing gaps in the schedule with newly arriving jobs. If no gap for a coming job is available EG-EDF rule uses Earliest Deadline First (EDF) strategy for including new job into the existing schedule. Such schedule is then optimized using the Tabu search algorithm mov- ing jobs into earliest gaps again. Scheduling choices are taken to meet the Quality of Service (QoS) requested by the submitted jobs, and to optimize the usage of hardware resources. We compared the proposed solution with some of the most common queue-based scheduling algo- rithms like FCFS, EASY back ̄lling, and Flexible back ̄lling. Experi- ments shows that EG-EDF rule is able to compute good assignments, often with shorter algorithm runtime w.r.t. the other queue-based al- gorithms. Further Tabu search optimization results in higher QoS and machine usage while keeping the algorithm runtime reasonable.DOI: 10.1007/978-0-387-09457-1_15
Metrics:
See at:
www.fi.muni.cz 
| doi.org | CNR IRIS | CNR IRIS | www.springerlink.com
2011
Conference article
Restricted
A parallel code for time independent quantum reactive scattering on CPU-GPU platforms
Baraglia R, Bravi M, Capannini G, Laganà A, Zambonini, E
The innovative architecture of GPUs has been exploited to the end of implementing an efficient version of the time independent quantum reactive scattering ABC code. The intensive usage of the code as a computational engine for several molecular calculations and crossed beams experiment simulations has prompted a detailed analysis of the utilization of the innovative features of the GPU architecture. ABC has shown to rely on a heavy usage of blocks of recursive sequences of linear algebra matrix operations whose performances vary significantly with the input and the section of the code. This has requested the evaluation of the suitability of different implementation strategies for the various parts of ABC. The outcomes of the related test runs are discussed in the paper.DOI: 10.1007/978-3-642-21931-3_32
Metrics:
Baraglia R, Bravi M, Capannini G, Laganà A, Zambonini, E
The innovative architecture of GPUs has been exploited to the end of implementing an efficient version of the time independent quantum reactive scattering ABC code. The intensive usage of the code as a computational engine for several molecular calculations and crossed beams experiment simulations has prompted a detailed analysis of the utilization of the innovative features of the GPU architecture. ABC has shown to rely on a heavy usage of blocks of recursive sequences of linear algebra matrix operations whose performances vary significantly with the input and the section of the code. This has requested the evaluation of the suitability of different implementation strategies for the various parts of ABC. The outcomes of the related test runs are discussed in the paper.DOI: 10.1007/978-3-642-21931-3_32
Metrics:
See at:
doi.org | CNR IRIS | CNR IRIS | www.springerlink.com
1983
Other
Open Access
2005
Journal article
Open Access
A static mapping heuristics to map parallel applications to heterogeneous computing systems
Baraglia R, Ferrini R, Ritrovato P
In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors . The general problem of mapping tasks to machines is a well known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called Heterogeneous Multi-phase Mapping (HMM), that permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the HC system is most suitable for executing a task. We compare HMM with four different leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach.Source: CONCURRENCY AND COMPUTATION, vol. 17 (issue 13), pp. 1579-1605
DOI: 10.1002/cpe.902
Metrics:
Baraglia R, Ferrini R, Ritrovato P
In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors . The general problem of mapping tasks to machines is a well known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called Heterogeneous Multi-phase Mapping (HMM), that permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the HC system is most suitable for executing a task. We compare HMM with four different leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach.Source: CONCURRENCY AND COMPUTATION, vol. 17 (issue 13), pp. 1579-1605
DOI: 10.1002/cpe.902
Metrics:
See at:
Concurrency and Computation Practice and Experience | dl.acm.org | Concurrency and Computation Practice and Experience | CNR IRIS | CNR IRIS
2006
Journal article
Restricted
HMM: a static mapping algorithm to map parallel applications on grids
Baraglia R, Ferrini R, Ritrovato P
In this paper we present a static mapping heuristic, called Heterogeneous Multi-phase Mapping (HMM), which allows a suboptimal mapping of a parallel program onto a metacomputer to minimize the program execution time. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application. Moreover, it uses a local search technique together with the tabu search meta-heuristic. The experimental results show that the proposed approach performs well promising a significant potential to develop efficient mapping solutions for metacomputers.
Baraglia R, Ferrini R, Ritrovato P
In this paper we present a static mapping heuristic, called Heterogeneous Multi-phase Mapping (HMM), which allows a suboptimal mapping of a parallel program onto a metacomputer to minimize the program execution time. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application. Moreover, it uses a local search technique together with the tabu search meta-heuristic. The experimental results show that the proposed approach performs well promising a significant potential to develop efficient mapping solutions for metacomputers.
2007
Journal article
Restricted
Dynamic personalization of Web sites without user intervention
Baraglia R, Silvestri F
The Web is an integral part of today's busi- ness dealings. Companies and institutions exploit the Web to conduct their business; customers make daily use of the Net to per- form all kinds of transactions. In addition, most users browse through pages of per- sonal interest. The Web, as we know, is massive and its data collected from count- less sources. Consequently, search tools should be able to accurately extract, filter, and select what is "hidden" from such tools.Source: COMMUNICATIONS OF THE ACM, vol. 50 (issue 2), pp. 63-67
DOI: 10.1145/1216016.1216022
Metrics:
Baraglia R, Silvestri F
The Web is an integral part of today's busi- ness dealings. Companies and institutions exploit the Web to conduct their business; customers make daily use of the Net to per- form all kinds of transactions. In addition, most users browse through pages of per- sonal interest. The Web, as we know, is massive and its data collected from count- less sources. Consequently, search tools should be able to accurately extract, filter, and select what is "hidden" from such tools.Source: COMMUNICATIONS OF THE ACM, vol. 50 (issue 2), pp. 63-67
DOI: 10.1145/1216016.1216022
Metrics:
See at:
dl.acm.org | Communications of the ACM | CNR IRIS | CNR IRIS
2003
Conference article
Restricted
Multi-FPGA Systems Synthesis by Means of Evolutionary Computation
Hidalgo Ji, Fernández F, Lanchares J, Sánchez J M, Hermida R, Tomassini M, Baraglia R, Perego R, Garnica O
Multi-FPGA systems (MFS) are used for a great variety of applications, for instance, dynamically re-configurable hardware applications, digital circuit emulation, and numerical computation. There are a great variety of boards for MFS implementation. In this paper a methodology for MFS design is presented. The techniques used are evolutionary programs and they solve all of the design tasks (partitioning placement and routing). Firstly a hybrid compact genetic algorithm solves the partitioning problem and then genetic programming is used to obtain a solution for the two other tasks.
Hidalgo Ji, Fernández F, Lanchares J, Sánchez J M, Hermida R, Tomassini M, Baraglia R, Perego R, Garnica O
Multi-FPGA systems (MFS) are used for a great variety of applications, for instance, dynamically re-configurable hardware applications, digital circuit emulation, and numerical computation. There are a great variety of boards for MFS implementation. In this paper a methodology for MFS design is presented. The techniques used are evolutionary programs and they solve all of the design tasks (partitioning placement and routing). Firstly a hybrid compact genetic algorithm solves the partitioning problem and then genetic programming is used to obtain a solution for the two other tasks.
2002
Journal article
Restricted
Metay: a Web-based metacomputing problem-solving environment for building complex applications
Baraglia R, Laforenza D
In this article we describe the main features of Meta , a software tool developed at CNUCE-CNR to build PSEs for the execution of complex applications on a Web-based metacomputer. This tool is designed to supply a completely transparent support to the user, who thus does not need to be aware of the location and the allocation of computing resources.Source: ERCIM NEWS, vol. 45, pp. 21-22
Baraglia R, Laforenza D
In this article we describe the main features of Meta , a software tool developed at CNUCE-CNR to build PSEs for the execution of complex applications on a Web-based metacomputer. This tool is designed to supply a completely transparent support to the user, who thus does not need to be aware of the location and the allocation of computing resources.Source: ERCIM NEWS, vol. 45, pp. 21-22
2004
Conference article
Restricted
An online recommender system for large Web sites
Baraglia R, Silvestri F
In this paper we propose a WUM recommender system, called SUGGEST 3.0, that dynamically generates links to pages that have not yet been visited by a user and might be of his potential interest. Differently from the recommender systems proposed so far, SUGGEST 3.0 does not make use of any off-line component, and is able to manage Web sites made up of pages dynamically generated. To this purpose SUGGEST 3.0 incrementally builds and maintains historical information by means of an incremental graph partitioning algorithm, requiring no off-line component. The main innovation proposed here is a novel strategy that can be used to manage large Web sites. Experiments, conducted in order to evaluate SUGGEST 3.0 performance, demonstrated that our system is able to anticipate users' requests that will be made farther in the future, introducing a limited overhead on the Web server activity.DOI: 10.1109/wi.2004.10158
Metrics:
Baraglia R, Silvestri F
In this paper we propose a WUM recommender system, called SUGGEST 3.0, that dynamically generates links to pages that have not yet been visited by a user and might be of his potential interest. Differently from the recommender systems proposed so far, SUGGEST 3.0 does not make use of any off-line component, and is able to manage Web sites made up of pages dynamically generated. To this purpose SUGGEST 3.0 incrementally builds and maintains historical information by means of an incremental graph partitioning algorithm, requiring no off-line component. The main innovation proposed here is a novel strategy that can be used to manage large Web sites. Experiments, conducted in order to evaluate SUGGEST 3.0 performance, demonstrated that our system is able to anticipate users' requests that will be made farther in the future, introducing a limited overhead on the Web server activity.DOI: 10.1109/wi.2004.10158
Metrics:
See at:
CNR IRIS | ieeexplore.ieee.org | CNR IRIS | xplorestaging.ieee.org
2004
Conference article
Restricted
An online recommender system
Baraglia R, Silvestri F
One of the most important class of Data Mining applications is the so called 'Web Mining Systems' which analyzes and extracts important and non-trivial knowledge from Web related data. Typical applications of Web Mining are represented by the personalization or recommender systems. These systems are aimed to extract knowledge from the analysis of historical information of a web server in order to improve the web site expressiveness in terms of readability and content availability. Typically, these systems are made up of two parts. One, which is usually executed off-line, analyzes the server access logs in order to find a suitable categorization, and another, which is usually executed online, classifies the active requests, according to the previous off-line analysis. In this paper we propose SUGGEST 2.0 a recommender system which differently from previously proposed WUM systems does not make use of an off-line component. Moreover, in the last part of the paper, we analyze the quality of the generated suggestions and the performance of our solution. To this purpose we also introduce a new quality metric which try to estimate the effectiveness of a recommender system as the capacity to anticipate users' requests that will be issued farther in the future.
Baraglia R, Silvestri F
One of the most important class of Data Mining applications is the so called 'Web Mining Systems' which analyzes and extracts important and non-trivial knowledge from Web related data. Typical applications of Web Mining are represented by the personalization or recommender systems. These systems are aimed to extract knowledge from the analysis of historical information of a web server in order to improve the web site expressiveness in terms of readability and content availability. Typically, these systems are made up of two parts. One, which is usually executed off-line, analyzes the server access logs in order to find a suitable categorization, and another, which is usually executed online, classifies the active requests, according to the previous off-line analysis. In this paper we propose SUGGEST 2.0 a recommender system which differently from previously proposed WUM systems does not make use of an off-line component. Moreover, in the last part of the paper, we analyze the quality of the generated suggestions and the performance of our solution. To this purpose we also introduce a new quality metric which try to estimate the effectiveness of a recommender system as the capacity to anticipate users' requests that will be issued farther in the future.
2005
Conference article
Restricted
Medical imaging demonstrator on a distributed virtual organisation
Baraglia R, Demi M, Di Bona S, Fontanelli R, Guerri D, Salvetti O
In several fields of the healthcare, there is a wide use of imaging techniques for diagnostic purposes, which usually lead to the acquisition of large sequences of images that are not easily analysed by the experts. The automatic processing of the events monitored represents an important support for the diagnosis. In this paper, we present a distributed decision support system for image classification based on neural networks. The applications presented are multidisciplinary, computational intensive and component based; therefore, a virtual organisation exploiting the GRID paradigm has been introduced in order to guarantee good performances of the diagnostic procedure and reliable results.
Baraglia R, Demi M, Di Bona S, Fontanelli R, Guerri D, Salvetti O
In several fields of the healthcare, there is a wide use of imaging techniques for diagnostic purposes, which usually lead to the acquisition of large sequences of images that are not easily analysed by the experts. The automatic processing of the events monitored represents an important support for the diagnosis. In this paper, we present a distributed decision support system for image classification based on neural networks. The applications presented are multidisciplinary, computational intensive and component based; therefore, a virtual organisation exploiting the GRID paradigm has been introduced in order to guarantee good performances of the diagnostic procedure and reliable results.
2001
Conference article
Unknown
A parallel compact genetic algorithm for multi-FPGA partitioning
Hidalgo J. I., Baraglia R. Perego R., Lanchares J., Tirade F.
In this paper we investigate the design of a compact genetic algorithm to solve Multi-FPGA Partitioning problems. Nowadays Multi-FPGA systems are used for a great variety of applications such as dynamically re-configurable hardware applications, digital circuit emulation, and numerical computation. Both a sequential and a parallel version of a compact genetic algorithm (cGA) have been designed and implemented on a cluster of workstations. The peculiarities of the cGA permits to save memory in order to address large Multi-FPGA Parfitioning problems, while the exploitation of parallelism allows to reduce execution times. The good results achieved on several experiments conduced on different Multi-FPGA Partitioning instances show that this solution is viable to solve Multi-FPGA Partitioning problems.Source: Euromicro Workshop on Parallel and Distributed Processing, pp. 113–120, Mantova, Italy, 2001
Hidalgo J. I., Baraglia R. Perego R., Lanchares J., Tirade F.
In this paper we investigate the design of a compact genetic algorithm to solve Multi-FPGA Partitioning problems. Nowadays Multi-FPGA systems are used for a great variety of applications such as dynamically re-configurable hardware applications, digital circuit emulation, and numerical computation. Both a sequential and a parallel version of a compact genetic algorithm (cGA) have been designed and implemented on a cluster of workstations. The peculiarities of the cGA permits to save memory in order to address large Multi-FPGA Parfitioning problems, while the exploitation of parallelism allows to reduce execution times. The good results achieved on several experiments conduced on different Multi-FPGA Partitioning instances show that this solution is viable to solve Multi-FPGA Partitioning problems.Source: Euromicro Workshop on Parallel and Distributed Processing, pp. 113–120, Mantova, Italy, 2001
See at: CNR ExploRA
2001
Conference article
Open Access
A parallel hybrid heuristic for the TSP
Baraglia R, Hidalgo Pèrez I, Perego R
In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.DOI: 10.1007/3-540-45365-2_20
Metrics:
Baraglia R, Hidalgo Pèrez I, Perego R
In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.DOI: 10.1007/3-540-45365-2_20
Metrics:
2007
Conference article
Open Access
A job scheduling framework for large computing farms
Capannini G, Baraglia R, Puppin D, Ricci L, Pasquali M
In this paper, we propose a new method, called Convergent Scheduling, for scheduling a continuous stream of batch jobs on the machines of large-scale computing farms. This method exploits a set of heuristics that guides the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a value that measures the degree of matching between a job and a machine. Scheduling choices are taken to meet the QoS requested by the submitted jobs, and optimizing the usage of hardware and software resources. We compared it with some of the most common job scheduling algorithms, i.e. Backfilling, and Earliest Deadline First. Convergent Scheduling is able to compute good assignments, while being a simple and modular algorithmDOI: 10.1145/1362622.1362695
Metrics:
Capannini G, Baraglia R, Puppin D, Ricci L, Pasquali M
In this paper, we propose a new method, called Convergent Scheduling, for scheduling a continuous stream of batch jobs on the machines of large-scale computing farms. This method exploits a set of heuristics that guides the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a value that measures the degree of matching between a job and a machine. Scheduling choices are taken to meet the QoS requested by the submitted jobs, and optimizing the usage of hardware and software resources. We compared it with some of the most common job scheduling algorithms, i.e. Backfilling, and Earliest Deadline First. Convergent Scheduling is able to compute good assignments, while being a simple and modular algorithmDOI: 10.1145/1362622.1362695
Metrics:
See at:
www.di.unipi.it | dl.acm.org | doi.org | CNR IRIS | CNR IRIS
2007
Conference article
Restricted
Backfilling strategies for scheduling streams of jobs on computational farms
Techiouba A, Capannini G, Baraglia R, Puppin D, Pasquali M, Ricci L
This paper presents a set of strategies for scheduling a stream of batch jobs on the machines of a heterogeneous computational farm. Our proposal is based on a flexible backfilling, which schedules jobs according to a priority assigned to each jobs submitted for the execution. Priority values are computed as a result of a set of heuristics whose main goal is both to improve resources utilization and to meet the QoS requirements of the jobs. The heuristics consider the deadlines of the jobs, their estimated execution time and aging in the scheduling queue. Furthermore, the set of software licenses required by a job is also considered. The different proposals have been compared through simulations. Performance figures show the applicability of our approach.
Techiouba A, Capannini G, Baraglia R, Puppin D, Pasquali M, Ricci L
This paper presents a set of strategies for scheduling a stream of batch jobs on the machines of a heterogeneous computational farm. Our proposal is based on a flexible backfilling, which schedules jobs according to a priority assigned to each jobs submitted for the execution. Priority values are computed as a result of a set of heuristics whose main goal is both to improve resources utilization and to meet the QoS requirements of the jobs. The heuristics consider the deadlines of the jobs, their estimated execution time and aging in the scheduling queue. Furthermore, the set of software licenses required by a job is also considered. The different proposals have been compared through simulations. Performance figures show the applicability of our approach.
2009
Conference article
Restricted
A priority-based multilevel scheduler for batch jobs on grids
Capannini G, Baraglia R, Pasquali M, Ricci L, Laforenza D
During the last decades, the architectures devoted to the high performance computing changed their shape and structure several times. From the early SMP machines to the Clusters of computers, through the Computational Grids to nowadays Computing Clouds. If on one side this evolution brought to computing platform able to provide several Petaflops, on the other side the increased amount of computing power, obtained through the usage of thousands computer in parallel makes more and more complex an effective and efficient management of resources. In this paper, we propose a multicriteria job scheduler for scheduling a continuous stream of batch jobs on large-scale computing farms, called Convergent Scheduling 2.0 (CS 2.0), which is an enhancement of the scheduler described in [3]. CS 2.0 exploits a set of heuristics that drive the scheduler in taking decisions. Each heuristics manages a specific constraint, and contributes to compute the measurement of the matching degree between a job and a machine. Scheduling choices are taken both to meet the QoS requested by the submitted jobs and to optimize the exploitation of hardware and software resources. In order to validate CS 2.0, we compared it versus two common job scheduling algorithms: Easy and Flexible backfilling. CS 2.0 demonstrated to be able to compute good assignments that allow a better exploitation of resources with respect to the other algorithms.
Capannini G, Baraglia R, Pasquali M, Ricci L, Laforenza D
During the last decades, the architectures devoted to the high performance computing changed their shape and structure several times. From the early SMP machines to the Clusters of computers, through the Computational Grids to nowadays Computing Clouds. If on one side this evolution brought to computing platform able to provide several Petaflops, on the other side the increased amount of computing power, obtained through the usage of thousands computer in parallel makes more and more complex an effective and efficient management of resources. In this paper, we propose a multicriteria job scheduler for scheduling a continuous stream of batch jobs on large-scale computing farms, called Convergent Scheduling 2.0 (CS 2.0), which is an enhancement of the scheduler described in [3]. CS 2.0 exploits a set of heuristics that drive the scheduler in taking decisions. Each heuristics manages a specific constraint, and contributes to compute the measurement of the matching degree between a job and a machine. Scheduling choices are taken both to meet the QoS requested by the submitted jobs and to optimize the exploitation of hardware and software resources. In order to validate CS 2.0, we compared it versus two common job scheduling algorithms: Easy and Flexible backfilling. CS 2.0 demonstrated to be able to compute good assignments that allow a better exploitation of resources with respect to the other algorithms.
See at:
CNR IRIS | CNR IRIS | puma.isti.cnr.it