The design of parallel algorithms is studied in this paper. These algorithms are applicable to shared memory MIMD machines In this paper, the emphasis is put on the methods for design of the efficient parallel algori...The design of parallel algorithms is studied in this paper. These algorithms are applicable to shared memory MIMD machines In this paper, the emphasis is put on the methods for design of the efficient parallel algorithms. The design of efficient parallel algorithms should be based on the following considerationst algorithm parallelism and the hardware-parallelism; granularity of the parallel algorithm, algorithm optimization according to the underling parallel machine. In this paper , these principles are applied to solve a model problem of the PDE. The speedup of the new method is high. The results were tested and evaluated on a shared memory MIMD machine. The practical results were agree with the predicted performance.展开更多
In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not sa...In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not satisfy the delay constraint, so we can ensure that all paths be taken into account will meet the limit of delay constraint, then we find the least costly path in order to build a minimum cost multicast tree. Simulation results show that the algorithm is better than ESAMPH algorithm in performance.展开更多
In the“shared manufacturing”environment,based on fairness,shared manufacturing platforms often require manufacturing service enterprises to arrange production according to the principle of“order first,finish first...In the“shared manufacturing”environment,based on fairness,shared manufacturing platforms often require manufacturing service enterprises to arrange production according to the principle of“order first,finish first”which leads to a series of scheduling problems with fixed processing sequences.In this paper,two two-machine hybrid flow-shop problems with fixed processing sequences are studied.Each job has two tasks.The first task is flexible,which can be processed on either of the two machines,and the second task must be processed on the second machine after the first task is completed.We consider two objective functions:to minimize the makespan and tominimize the total weighted completion time.First,we show the problem for any one of the two objectives is ordinary NP-hard by polynomial-time Turing Reduction.Then,using the Continuous ProcessingModule(CPM),we design a dynamic programming algorithm for each case and calculate the time complexity of each algorithm.Finally,numerical experiments are used to analyze the effect of dynamic programming algorithms in practical operations.Comparative experiments show that these dynamic programming algorithms have comprehensive advantages over the branch and bound algorithm(a classical exact algorithm)and the discrete harmony search algorithm(a high-performance heuristic algorithm).展开更多
Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry,the coordinated scheduling problem of parallel machine production and transportation is investigated.The prob...Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry,the coordinated scheduling problem of parallel machine production and transportation is investigated.The problem takes into account the coordination of production and transportation before production as well as the disparities in machine spatial position and performance.A non-cooperative game model is established,considering the competition and self-interest behavior of jobs from different customers for machine resources.The job from different customers is mapped to the players in the game model,the corresponding optional processing machine and location are mapped to the strategy set,and the makespan of the job is mapped to the payoff.Then the solution of the scheduling model is transformed into the Nash equilibrium of the non-cooperative game model.A Nash equilibrium solution algorithm based on the genetic algorithm(NEGA)is designed,and the effective solution of approximate Nash equilibrium for the game model is realized.The fitness function,single-point crossover operator,and mutation operator are derived from the non-cooperative game model’s characteristics and the definition of Nash equilibrium.Rules are also designed to avoid the generation of invalid offspring chromosomes.The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes.Compared with other algorithms such as heuristic algorithms(FCFS,SPT,and LPT),the simulated annealing algorithm(SA),and the particle swarm optimization algorithm(PSO),experimental results show that the proposed NE-GA algorithm has obvious performance advantages.展开更多
Modern shared-memory multi-core processors typically have shared Level 2(L2)or Level 3(L3)caches.Cache bottlenecks and replacement strategies are the main problems of such architectures,where multiple cores try to acc...Modern shared-memory multi-core processors typically have shared Level 2(L2)or Level 3(L3)caches.Cache bottlenecks and replacement strategies are the main problems of such architectures,where multiple cores try to access the shared cache simultaneously.The main problem in improving memory performance is the shared cache architecture and cache replacement.This paper documents the implementation of a Dual-Port Content Addressable Memory(DPCAM)and a modified Near-Far Access Replacement Algorithm(NFRA),which was previously proposed as a shared L2 cache layer in a multi-core processor.Standard Performance Evaluation Corporation(SPEC)Central Processing Unit(CPU)2006 benchmark workloads are used to evaluate the benefit of the shared L2 cache layer.Results show improved performance of the multicore processor’s DPCAM and NFRA algorithms,corresponding to a higher number of concurrent accesses to shared memory.The new architecture significantly increases system throughput and records performance improvements of up to 8.7%on various types of SPEC 2006 benchmarks.The miss rate is also improved by about 13%,with some exceptions in the sphinx3 and bzip2 benchmarks.These results could open a new window for solving the long-standing problems with shared cache in multi-core processors.展开更多
Shared manufacturing is recognized as a new point-to-point manufac-turing mode in the digital era.Shared manufacturing is referred to as a new man-ufacturing mode to realize the dynamic allocation of manufacturing tas...Shared manufacturing is recognized as a new point-to-point manufac-turing mode in the digital era.Shared manufacturing is referred to as a new man-ufacturing mode to realize the dynamic allocation of manufacturing tasks and resources.Compared with the traditional mode,shared manufacturing offers more abundant manufacturing resources and flexible configuration options.This paper proposes a model based on the description of the dynamic allocation of tasks and resources in the shared manufacturing environment,and the characteristics of shared manufacturing resource allocation.The execution of manufacturing tasks,in which candidate manufacturing resources enter or exit at various time nodes,enables the dynamic allocation of manufacturing tasks and resources.Then non-dominated sorting genetic algorithm(NSGA-II)and multi-objective particle swarm optimization(MOPSO)algorithms are designed to solve the model.The optimal parameter settings for the NSGA-II and MOPSO algorithms have been obtained according to the experiments with various population sizes and iteration numbers.In addition,the proposed model’s efficiency,which considers the entries and exits of manufacturing resources in the shared manufacturing environment,is further demonstrated by the overlap between the outputs of the NSGA-II and MOPSO algorithms for optimal resource allocation.展开更多
In order to solve security problem of clustering algorithm, we proposed amethod to enhance the security of the well-known lowest-ID clustering algorithm. This method isbased on the idea of the secret sharing and the (...In order to solve security problem of clustering algorithm, we proposed amethod to enhance the security of the well-known lowest-ID clustering algorithm. This method isbased on the idea of the secret sharing and the (k, n) threshold cryptography, Each node, whetherclusterhead or ordinary member, holds a share of the global certificate, and any k nodes cancommunicate securely. There is no need for any clusterhead to execute extra functions more thanrouting. Our scheme needs some prior configuration before deployment, and can be used in criticalenvironment with small scale. The security-enhancement for Lowest-ID algorithm can also be appliedinto other clustering approaches with minor modification. The feasibility of this method wasverified bythe simulation results.展开更多
A new algorithm is proposed for underwater vehicles multi-path planning. This algorithm is based on fitness sharing genetic algorithm, clustering and evolution of multiple populations, which can keep the diversity of ...A new algorithm is proposed for underwater vehicles multi-path planning. This algorithm is based on fitness sharing genetic algorithm, clustering and evolution of multiple populations, which can keep the diversity of the solution path, and decrease the operating time because of the independent evolution of each subpopulation. The multi-path planning algorithm is demonstrated by a number of two-dimensional path planning problems. The results show that the multi-path planning algorithm has the following characteristics: high searching capability, rapid convergence and high reliability.展开更多
Edge computing devices are widely deployed.An important issue that arises is in that these devices suffer from security attacks.To deal with it,we turn to the blockchain technologies.The note in the alliance chain nee...Edge computing devices are widely deployed.An important issue that arises is in that these devices suffer from security attacks.To deal with it,we turn to the blockchain technologies.The note in the alliance chain need rules to limit write permissions.Alliance chain can provide security management functions,using these functions to meet the management between the members,certification,authorization,monitoring and auditing.This article mainly analyzes some requirements realization which applies to the alliance chain,and introduces a new consensus algorithm,generalized Legendre sequence(GLS)consensus algorithm,for alliance chain.GLS algorithms inherit the recognition and verification efficiency of binary sequence ciphers in computer communication and can solve a large number of nodes verification of key distribution issues.In the alliance chain,GLS consensus algorithm can complete node address hiding,automatic task sorting,task automatic grouping,task node scope confirmation,task address binding and stamp timestamp.Moreover,the GLS consensus algorithm increases the difficulty of network malicious attack.展开更多
Aiming at the problem of dynamic multicast service protection in multi-domain optical network, this paper proposes a dynamic multicast sharing protection algorithm based on fuzzy game in multi-domain optical network. ...Aiming at the problem of dynamic multicast service protection in multi-domain optical network, this paper proposes a dynamic multicast sharing protection algorithm based on fuzzy game in multi-domain optical network. The algorithm uses the minimum cost spanning tree strategy and fuzzy game theory. First, it virtualizes two planes to calculate the multicast tree and the multicast protection tree respectively. Then, it performs a fuzzy game to form a cooperative alliance to optimize the path composition of each multicast tree. Finally, it generates a pair of optimal multicast work tree and multicast protection tree for dynamic multicast services. The time complexity of the algorithm is O(k3 m2 n), where n represents the number of nodes in the networks, k represents the number of dynamic multicast requests, and m represents the number of destination nodes for each multicast request. The experimental results show that the proposed algorithm reduces significantly the blocking rate of dynamic multicast services, and improves the utilization of optical network resources within a certain number of dynamic multicast request ranges.展开更多
文摘The design of parallel algorithms is studied in this paper. These algorithms are applicable to shared memory MIMD machines In this paper, the emphasis is put on the methods for design of the efficient parallel algorithms. The design of efficient parallel algorithms should be based on the following considerationst algorithm parallelism and the hardware-parallelism; granularity of the parallel algorithm, algorithm optimization according to the underling parallel machine. In this paper , these principles are applied to solve a model problem of the PDE. The speedup of the new method is high. The results were tested and evaluated on a shared memory MIMD machine. The practical results were agree with the predicted performance.
文摘In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not satisfy the delay constraint, so we can ensure that all paths be taken into account will meet the limit of delay constraint, then we find the least costly path in order to build a minimum cost multicast tree. Simulation results show that the algorithm is better than ESAMPH algorithm in performance.
基金This work was partially supported by the Zhejiang Provincial Philosophy and Social Science Program of China(Grant No.19NDJC093YB)the National Social Science Foundation of China(Grant No.19BGL001)+1 种基金the Natural Science Foundation of Zhejiang Province of China(Grant No.LY19A010002)the Natural Science Foundation of Ningbo of China(The design of algorithms and cost-sharing rules for scheduling problems in shared manufacturing,Acceptance No.20211JCGY010241).
文摘In the“shared manufacturing”environment,based on fairness,shared manufacturing platforms often require manufacturing service enterprises to arrange production according to the principle of“order first,finish first”which leads to a series of scheduling problems with fixed processing sequences.In this paper,two two-machine hybrid flow-shop problems with fixed processing sequences are studied.Each job has two tasks.The first task is flexible,which can be processed on either of the two machines,and the second task must be processed on the second machine after the first task is completed.We consider two objective functions:to minimize the makespan and tominimize the total weighted completion time.First,we show the problem for any one of the two objectives is ordinary NP-hard by polynomial-time Turing Reduction.Then,using the Continuous ProcessingModule(CPM),we design a dynamic programming algorithm for each case and calculate the time complexity of each algorithm.Finally,numerical experiments are used to analyze the effect of dynamic programming algorithms in practical operations.Comparative experiments show that these dynamic programming algorithms have comprehensive advantages over the branch and bound algorithm(a classical exact algorithm)and the discrete harmony search algorithm(a high-performance heuristic algorithm).
基金supported in part by the Project of Liaoning BaiQianWan Talents ProgramunderGrand No.2021921089the Science Research Foundation of EducationalDepartment of Liaoning Province under Grand No.LJKQZ2021057 and WJGD2020001the Key Program of Social Science Planning Foundation of Liaoning Province under Grant L21AGL017.
文摘Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry,the coordinated scheduling problem of parallel machine production and transportation is investigated.The problem takes into account the coordination of production and transportation before production as well as the disparities in machine spatial position and performance.A non-cooperative game model is established,considering the competition and self-interest behavior of jobs from different customers for machine resources.The job from different customers is mapped to the players in the game model,the corresponding optional processing machine and location are mapped to the strategy set,and the makespan of the job is mapped to the payoff.Then the solution of the scheduling model is transformed into the Nash equilibrium of the non-cooperative game model.A Nash equilibrium solution algorithm based on the genetic algorithm(NEGA)is designed,and the effective solution of approximate Nash equilibrium for the game model is realized.The fitness function,single-point crossover operator,and mutation operator are derived from the non-cooperative game model’s characteristics and the definition of Nash equilibrium.Rules are also designed to avoid the generation of invalid offspring chromosomes.The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes.Compared with other algorithms such as heuristic algorithms(FCFS,SPT,and LPT),the simulated annealing algorithm(SA),and the particle swarm optimization algorithm(PSO),experimental results show that the proposed NE-GA algorithm has obvious performance advantages.
文摘Modern shared-memory multi-core processors typically have shared Level 2(L2)or Level 3(L3)caches.Cache bottlenecks and replacement strategies are the main problems of such architectures,where multiple cores try to access the shared cache simultaneously.The main problem in improving memory performance is the shared cache architecture and cache replacement.This paper documents the implementation of a Dual-Port Content Addressable Memory(DPCAM)and a modified Near-Far Access Replacement Algorithm(NFRA),which was previously proposed as a shared L2 cache layer in a multi-core processor.Standard Performance Evaluation Corporation(SPEC)Central Processing Unit(CPU)2006 benchmark workloads are used to evaluate the benefit of the shared L2 cache layer.Results show improved performance of the multicore processor’s DPCAM and NFRA algorithms,corresponding to a higher number of concurrent accesses to shared memory.The new architecture significantly increases system throughput and records performance improvements of up to 8.7%on various types of SPEC 2006 benchmarks.The miss rate is also improved by about 13%,with some exceptions in the sphinx3 and bzip2 benchmarks.These results could open a new window for solving the long-standing problems with shared cache in multi-core processors.
基金This work was supported by the Key Program of Social Science Planning Foundation of Liaoning Province under Grant L21AGL017.
文摘Shared manufacturing is recognized as a new point-to-point manufac-turing mode in the digital era.Shared manufacturing is referred to as a new man-ufacturing mode to realize the dynamic allocation of manufacturing tasks and resources.Compared with the traditional mode,shared manufacturing offers more abundant manufacturing resources and flexible configuration options.This paper proposes a model based on the description of the dynamic allocation of tasks and resources in the shared manufacturing environment,and the characteristics of shared manufacturing resource allocation.The execution of manufacturing tasks,in which candidate manufacturing resources enter or exit at various time nodes,enables the dynamic allocation of manufacturing tasks and resources.Then non-dominated sorting genetic algorithm(NSGA-II)and multi-objective particle swarm optimization(MOPSO)algorithms are designed to solve the model.The optimal parameter settings for the NSGA-II and MOPSO algorithms have been obtained according to the experiments with various population sizes and iteration numbers.In addition,the proposed model’s efficiency,which considers the entries and exits of manufacturing resources in the shared manufacturing environment,is further demonstrated by the overlap between the outputs of the NSGA-II and MOPSO algorithms for optimal resource allocation.
基金Supported by the National High Technology Re search and Development Program of China (2003AA142080)
文摘In order to solve security problem of clustering algorithm, we proposed amethod to enhance the security of the well-known lowest-ID clustering algorithm. This method isbased on the idea of the secret sharing and the (k, n) threshold cryptography, Each node, whetherclusterhead or ordinary member, holds a share of the global certificate, and any k nodes cancommunicate securely. There is no need for any clusterhead to execute extra functions more thanrouting. Our scheme needs some prior configuration before deployment, and can be used in criticalenvironment with small scale. The security-enhancement for Lowest-ID algorithm can also be appliedinto other clustering approaches with minor modification. The feasibility of this method wasverified bythe simulation results.
文摘A new algorithm is proposed for underwater vehicles multi-path planning. This algorithm is based on fitness sharing genetic algorithm, clustering and evolution of multiple populations, which can keep the diversity of the solution path, and decrease the operating time because of the independent evolution of each subpopulation. The multi-path planning algorithm is demonstrated by a number of two-dimensional path planning problems. The results show that the multi-path planning algorithm has the following characteristics: high searching capability, rapid convergence and high reliability.
基金We gratefully acknowledge anonymous reviewers who read drafts and made many helpful suggestions.This work is supported by the National Key Research and Development Program No.2018YFC0807002.
文摘Edge computing devices are widely deployed.An important issue that arises is in that these devices suffer from security attacks.To deal with it,we turn to the blockchain technologies.The note in the alliance chain need rules to limit write permissions.Alliance chain can provide security management functions,using these functions to meet the management between the members,certification,authorization,monitoring and auditing.This article mainly analyzes some requirements realization which applies to the alliance chain,and introduces a new consensus algorithm,generalized Legendre sequence(GLS)consensus algorithm,for alliance chain.GLS algorithms inherit the recognition and verification efficiency of binary sequence ciphers in computer communication and can solve a large number of nodes verification of key distribution issues.In the alliance chain,GLS consensus algorithm can complete node address hiding,automatic task sorting,task automatic grouping,task node scope confirmation,task address binding and stamp timestamp.Moreover,the GLS consensus algorithm increases the difficulty of network malicious attack.
基金supported by the National Natural Science Foundation of China (No.61402529)the Natural Science Basic Research Plan in Shanxi Province of China (No.2020JM-361)+1 种基金the Young and Middle-aged Scientific Research Backbone Projects of Engineering University of PAP (No.KYGG201905)the Basic Researchof Engineering University of PAP (Nos.WJY201920 and WJY202019)。
文摘Aiming at the problem of dynamic multicast service protection in multi-domain optical network, this paper proposes a dynamic multicast sharing protection algorithm based on fuzzy game in multi-domain optical network. The algorithm uses the minimum cost spanning tree strategy and fuzzy game theory. First, it virtualizes two planes to calculate the multicast tree and the multicast protection tree respectively. Then, it performs a fuzzy game to form a cooperative alliance to optimize the path composition of each multicast tree. Finally, it generates a pair of optimal multicast work tree and multicast protection tree for dynamic multicast services. The time complexity of the algorithm is O(k3 m2 n), where n represents the number of nodes in the networks, k represents the number of dynamic multicast requests, and m represents the number of destination nodes for each multicast request. The experimental results show that the proposed algorithm reduces significantly the blocking rate of dynamic multicast services, and improves the utilization of optical network resources within a certain number of dynamic multicast request ranges.
