Hardware/software partitioning is an essential step in hardware/software co-design.For large size problems,it is difficult to consider both solution quality and time.This paper presents an efficient GPU-based parallel...Hardware/software partitioning is an essential step in hardware/software co-design.For large size problems,it is difficult to consider both solution quality and time.This paper presents an efficient GPU-based parallel tabu search algorithm(GPTS)for HW/SW partitioning.A single GPU kernel of compacting neighborhood is proposed to reduce the amount of GPU global memory accesses theoretically.A kernel fusion strategy is further proposed to reduce the amount of GPU global memory accesses of GPTS.To further minimize the transfer overhead of GPTS between CPU and GPU,an optimized transfer strategy for GPU-based tabu evaluation is proposed,which considers that all the candidates do not satisfy the given constraint.Experiments show that GPTS outperforms state-of-the-art work of tabu search and is competitive with other methods for HW/SW partitioning.The proposed parallelization is significant when considering the ordinary GPU platform.展开更多
Urban Transit Scheduling Problem (UTSP) is concerned with determining reliable transit schedules for buses and drivers by considering the preferences of both passengers and operators based on the demand and the set of...Urban Transit Scheduling Problem (UTSP) is concerned with determining reliable transit schedules for buses and drivers by considering the preferences of both passengers and operators based on the demand and the set of transit routes. This paper considered a UTSP which consisted of frequency setting, timetabling, and simultaneous bus and driver scheduling. A mixed integer multiobjective model was constructed to optimize the frequency of the routes by minimizing the number of buses, passenger’s waiting times and overcrowding. The model was further extended by incorporating timeslots in determining the frequencies during peak and off-peak hours throughout the time period. The timetabling problem studied two different scenarios which reflected the preferences of passengers and operators to assign the bus departure times at the first and last stop of a route. A set covering model was then adopted to minimize the number of buses and drivers simultaneously. A parallel tabu search algorithm was proposed to solve the problem by modifying the initialization process and incorporating intensification and diversification approaches to guide the search effectively from the different feasible domain in finding optimal solutions with lesser computational effort. Computational experiments were conducted on the well-known Mandl’s and Mumford’s benchmark networks to assess the effectiveness of the proposed algorithm. Competitive results are reported based on the performance metrics, as compared to other algorithms from the literature.展开更多
基金This paper was supported by the National Natural Science Foundation of China(Grant No.61472289)National Key Research and Development Project(2016YFC0106305).We also would like to thank the anonymous reviewers for their valuable and constructive comments.
文摘Hardware/software partitioning is an essential step in hardware/software co-design.For large size problems,it is difficult to consider both solution quality and time.This paper presents an efficient GPU-based parallel tabu search algorithm(GPTS)for HW/SW partitioning.A single GPU kernel of compacting neighborhood is proposed to reduce the amount of GPU global memory accesses theoretically.A kernel fusion strategy is further proposed to reduce the amount of GPU global memory accesses of GPTS.To further minimize the transfer overhead of GPTS between CPU and GPU,an optimized transfer strategy for GPU-based tabu evaluation is proposed,which considers that all the candidates do not satisfy the given constraint.Experiments show that GPTS outperforms state-of-the-art work of tabu search and is competitive with other methods for HW/SW partitioning.The proposed parallelization is significant when considering the ordinary GPU platform.
文摘Urban Transit Scheduling Problem (UTSP) is concerned with determining reliable transit schedules for buses and drivers by considering the preferences of both passengers and operators based on the demand and the set of transit routes. This paper considered a UTSP which consisted of frequency setting, timetabling, and simultaneous bus and driver scheduling. A mixed integer multiobjective model was constructed to optimize the frequency of the routes by minimizing the number of buses, passenger’s waiting times and overcrowding. The model was further extended by incorporating timeslots in determining the frequencies during peak and off-peak hours throughout the time period. The timetabling problem studied two different scenarios which reflected the preferences of passengers and operators to assign the bus departure times at the first and last stop of a route. A set covering model was then adopted to minimize the number of buses and drivers simultaneously. A parallel tabu search algorithm was proposed to solve the problem by modifying the initialization process and incorporating intensification and diversification approaches to guide the search effectively from the different feasible domain in finding optimal solutions with lesser computational effort. Computational experiments were conducted on the well-known Mandl’s and Mumford’s benchmark networks to assess the effectiveness of the proposed algorithm. Competitive results are reported based on the performance metrics, as compared to other algorithms from the literature.
