Various intelligent applications based on non-chain DNN models are widely used in Internet of Things(IoT)scenarios.However,resource-constrained Io T devices usually cannot afford the heavy computation burden and canno...Various intelligent applications based on non-chain DNN models are widely used in Internet of Things(IoT)scenarios.However,resource-constrained Io T devices usually cannot afford the heavy computation burden and cannot guarantee the strict inference latency requirements of non-chain DNN models.Multi-device collaboration has become a promising paradigm for achieving inference acceleration.However,existing works neglect the possibility of inter-layer parallel execution,which fails to exploit the parallelism of collaborating devices and inevitably prolongs the overall completion latency.Thus,there is an urgent need to pay attention to the issue of non-chain DNN inference acceleration with multi-device collaboration based on inter-layer parallel.Three major challenges to be overcome in this problem include exponential computational complexity,complicated layer dependencies,and intractable execution location selection.To this end,we propose a Topological Sorting Based Bidirectional Search(TSBS)algorithm that can adaptively partition non-chain DNN models and select suitable execution locations at layer granularity.More specifically,the TSBS algorithm consists of a topological sorting subalgorithm to realize parallel execution with low computational complexity under complicated layer parallel constraints,and a bidirectional search subalgorithm to quickly find the suitable execution locations for non-parallel layers.Extensive experiments show that the TSBS algorithm significantly outperforms the state-of-the-arts in the completion latency of non-chain DNN inference,a reduction of up to 22.69%.展开更多
An approach to make heterogeneous devices cooperate with each other to provide ubiquitous service remains a longstanding challenge in ubiquitous environments. In addition, when multi-user request ubiquitous services s...An approach to make heterogeneous devices cooperate with each other to provide ubiquitous service remains a longstanding challenge in ubiquitous environments. In addition, when multi-user request ubiquitous services simultaneously, the arbitrariness in resource allocation process easily leads to non-equilibrium of qualities of multiuser's services. Thus, How to design an effective heterogeneous devices cooperation mechanism that meet the QoS requirements and also equilibrate QoS among multi-user's services becomes a very tough problem. In the paper, Equilibrium Index and Theil Utility function are imported to establish a multidevice equilibrium cooperation model, which is benefit for resource allocation in ubiquitous environments. Then a Theil-Equilibrium based Cooperation Mechanism for multi-service is proposed. Firstly, in order to simplify calculating, a dimensionless processing is introduced. After that, a cooperation approach with Theil-Utility Heuristic algorithm is designed to choose the best solution for the simplified model. At last, the mechanism is simulated in a smart home scenario. The simulation results show that this mechanism outperforms non-equilibrium method by improving almost 40% in internal equilibrium with just reducing 0-2% in the total utility ofall the requested ubiquitous services. These data show that the proposed mechanism performs well in equilibrating qualities of multi-user's ubiquitous services.展开更多
基金supported by the National Key Research and Development Program of China(2021YFB2900102)the National Natural Science Foundation of China(No.62072436 and No.62202449)。
文摘Various intelligent applications based on non-chain DNN models are widely used in Internet of Things(IoT)scenarios.However,resource-constrained Io T devices usually cannot afford the heavy computation burden and cannot guarantee the strict inference latency requirements of non-chain DNN models.Multi-device collaboration has become a promising paradigm for achieving inference acceleration.However,existing works neglect the possibility of inter-layer parallel execution,which fails to exploit the parallelism of collaborating devices and inevitably prolongs the overall completion latency.Thus,there is an urgent need to pay attention to the issue of non-chain DNN inference acceleration with multi-device collaboration based on inter-layer parallel.Three major challenges to be overcome in this problem include exponential computational complexity,complicated layer dependencies,and intractable execution location selection.To this end,we propose a Topological Sorting Based Bidirectional Search(TSBS)algorithm that can adaptively partition non-chain DNN models and select suitable execution locations at layer granularity.More specifically,the TSBS algorithm consists of a topological sorting subalgorithm to realize parallel execution with low computational complexity under complicated layer parallel constraints,and a bidirectional search subalgorithm to quickly find the suitable execution locations for non-parallel layers.Extensive experiments show that the TSBS algorithm significantly outperforms the state-of-the-arts in the completion latency of non-chain DNN inference,a reduction of up to 22.69%.
基金partially supported by the Funds for Creative Research Groups of China(61121061)National Natural Science Foundation of China(61302078,61272515)+3 种基金863 Program(2011AA01A102)Ph.D.Programs Foundation of Ministry of Education of China(20110005110011)Beijing Higher Education Young Elite Teacher Project(YETP0476)Fundamental Research Funds for the Central Universities(2012RC0609)
文摘An approach to make heterogeneous devices cooperate with each other to provide ubiquitous service remains a longstanding challenge in ubiquitous environments. In addition, when multi-user request ubiquitous services simultaneously, the arbitrariness in resource allocation process easily leads to non-equilibrium of qualities of multiuser's services. Thus, How to design an effective heterogeneous devices cooperation mechanism that meet the QoS requirements and also equilibrate QoS among multi-user's services becomes a very tough problem. In the paper, Equilibrium Index and Theil Utility function are imported to establish a multidevice equilibrium cooperation model, which is benefit for resource allocation in ubiquitous environments. Then a Theil-Equilibrium based Cooperation Mechanism for multi-service is proposed. Firstly, in order to simplify calculating, a dimensionless processing is introduced. After that, a cooperation approach with Theil-Utility Heuristic algorithm is designed to choose the best solution for the simplified model. At last, the mechanism is simulated in a smart home scenario. The simulation results show that this mechanism outperforms non-equilibrium method by improving almost 40% in internal equilibrium with just reducing 0-2% in the total utility ofall the requested ubiquitous services. These data show that the proposed mechanism performs well in equilibrating qualities of multi-user's ubiquitous services.
