Hierarchical Partitioning Techniques for Structured Adaptive Mesh Refinement Applications

This paper presents the design and preliminary evaluation of hierarchical partitioning and load-balancing techniques for distributed structured adaptive mesh refinement (SAMR) applications. The overall goal of these techniques is to enable the load distribution to reflect the state of the adaptive grid hierarchy and exploit it to reduce synchronization requirements, improve load-balance, and enable concurrent communications and incremental redistribution. The hierarchical partitioning algorithm (HPA) partitions the computational domain into subdomains and assigns them to hierarchical processor groups. Two variants of HPA are presented in this paper. The static hierarchical partitioning algorithm (SHPA) assigns portions of overall load to processor groups. In SHPA, the group size and the number of processors in each group is setup during initialization and remains unchanged during application execution. It is experimentally shown that SHPA reduces communication costs as compared to the Non-HPA scheme, and reduces overall application execution time by up to 59%. The adaptive hierarchical partitioning algorithm (AHPA) dynamically partitions the processor pool into hierarchical groups that match the structure of the adaptive grid hierarchy. Initial evaluations of AHPA show that it can reduce communication costs by up to 70%.     

Compact Mathematical Formulation for Graph Partitioning

The graph partitioning problem consists of dividing the vertices of a graph into clusters, such that the weight of the edges crossing between clusters is minimized. We present a new compact mathematical formulation of this problem, based on the use of binary representation for the index of clusters assigned to vertices. This new formulation is almost minimal in terms of the number of variables and constraints and of the density of the constraint matrix. Its linear relaxation brings a very fast computational resolution, compared with the standard one.Experiments were conducted on classical large benchmark graphs designed for comparing heuristic methods. On one hand, these experiments show that the new formulation is surprisingly less time efficient than expected on general k-partitioning problems. On the other hand, the new formulation applied on bisection problems allows to obtain the optimum solution for about ten instances, where only best upper bounds were previously known.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

含柔性多状态开关的配电网分区方法

柔性多状态开关是一种新型智能配电装置。结合柔性多状态开关的功能特点,提出了含柔性多状态开关的配电网分区条件。以多层图分割理论框架为基础,提出了由粗化、分区和还原阶段构成的分区方法。在粗化过程中,提出了基于最短电气距离的粗化方法,使用贪婪图生长算法完成初始分区,并在还原阶段提出了基于路径搜索的还原方法。分区方法不仅能够优化配电网的运行指标,还能够提高配电网的可控性和灵活性。通过IEEE 118节点配电网算例对所述分区方法进行了说明和验证,并结合柔性多状态开关的调控对分区效果进行了进一步分析。结果表明,该方法能够改善配电网的日均馈线负载均衡度,并能够和柔性多状态开关的调控相配合,进一步改善配电网每一时刻的馈线负载均衡度和电压分布。     

Extraction of anionic dyes with ionic liquid–nonionic surfactant aqueous two-phase system

The cloud point of nonionic surfactant (Triton X-114) in ionic liquid ([Bmim]Cl) aqueous solution exhibits as increase and then decrease and increase again with the increase of ionic liquid (IL) content, which is the origin of an IL–nonionic surfactant aqueous two-phase system. The nonionic surfactant-rich phase coexists with a high content of IL aqueous solution phase in the IL–nonionic surfactant aqueous two-phase system. The partitioning of various ionic dyes indicates that anionic species exhibit a high partitioning coefficient between the IL-rich phase and the nonionic surfactant-rich phase.     

自适应连续多级分区与初始阈值估计的快速模板匹配方法

归一化互相关测度在光照改变时比采用绝对差之和测度（SAD）要稳定，但是归一化互相关测度的缺陷在于它的计算量非常大。为此，提出了一种结合自适应连续多级分区和初始阈值估计的基于归一化互相关（NCC）的快速模板匹配算法。根据模板图像中不同模块的梯度值，将模板图像进行逐级分区，通过分区顺序将互相关之和分为不同的层，得到各层互相关的上界，运用柯西-施不等式得到上界间的关系，形成自适应连续多级分区淘汰方法。同时，为了加快匹配速度，利用初始阈值估计产生一个较大的边界阈值，以淘汰初始搜索时的大量非匹配点，减少搜索点数目。实验结果表明:所提出的算法具有较好的鲁棒性，且算法的执行速度优于传统算法。     

Progressive filling partitioning and mapping algorithm for Spark based on allocation fitness degree

The job execution mechanism of Spark was analyzed,task efficiency model and Shuffle model were established,then allocation fitness degree (AFD) was defined and the optimization goal was put forward.On the basis of the model definition,the progressive filling partitioning and mapping algorithm (PFPM) was proposed.PFPM established the data distribution scheme adapting Reducers’ computing ability to decrease synchronous latency during Shuffle process and increase cluster the computing efficiency.The experiments demonstrate that PFPM could improve the rationality of workload distribution in Shuffle and optimize the execution efficiency of Spark.     

Growth of organic films on indoor surfaces

We present a model for the growth of organic films on impermeable indoor surfaces. The model couples transport through a gas‐side boundary layer adjacent to the surface with equilibrium partitioning of semivolatile organic compounds (SVOCs) between the gas phase and the surface film. Model predictions indicate that film growth would primarily be influenced by the gas‐phase concentration of SVOCs with octanol‐air partitioning (K_oa) values in the approximate range 10≤log K_oa≤13. Within the relevant range, SVOCs with lower values will equilibrate with the surface film more rapidly. Over time, the film becomes relatively enriched in species with higher log K_oa values, while the proportion of gas‐phase SVOCs not in equilibrium with the film decreases. Given stable airborne SVOC concentrations, films grow at faster rates initially and then subsequently diminish to an almost steady growth rate. Once an SVOC is equilibrated with the film, its mass per unit film volume remains constant, while its mass per unit area increases in proportion to overall film thickness. The predictions of the conceptual model and its mathematical embodiment are generally consistent with results reported in the peer‐reviewed literature.     

A new approach for data partitioning through high dimensional model representation

A multivariate function f(x ₁, …, x _N ) can be evaluated via interpolation if its values are given at a finite number nodes of a hyperprismatic grid in the space of independent variables x ₁, x ₂, …, x _N . Interpolation is a way to characterize an infinite data structure (function) by a finite number of data approximately. Hence it leaves an infinite arbitrariness unless a mathematical structure with finite number of flexibilities is imposed for the unknown function. Imposed structure has finite dimensionality. When the dimensionality increases unboundedly, the complexities grow rapidly in the standard methods. The main purpose here is to partition the given multivariate data into a set of low-variate data by using high dimensional model representation (HDMR) and then, to interpolate each individual data in the set via Lagrange interpolation formula. As a result, computational complexity of the given problem and needed CPU time to obtain the results through a series of programs in computers decrease.     

A FRAMEWORK FOR PARTITIONING STRUCTURED GRIDS WITH INHOMOGENEOUS WORKLOAD

A framework is presented for partitioning arrays with irregular workload. Within the framework structured and unstructured methods are combined in a new approach to partition data, based on blocks and block operations. A new variant of the recursive spectral bisection method suitable in this context is suggested. The use of the framework is demonstrated for a real life application, ocean modeling of the Baltic Sea. In this case study, the new approach gives very good results while standard partitioning methods cannot fulfill all the listed requirements. The operations have been implemented in a Fortran 90 software package with an object-oriented design.