Parallel Processing Letters

Mehrotra, Johnson, and Nemhauser (1998) [Management Science 44, pp. 1100–1114] addressed a problem for political districting and developed an optimization based heuristic to find good districting plans which partition the population units into contiguous districts with equal populations. Their case study found a good South Carolina plan at a penalty cost of 68. This paper develops a strong integer programming model identifying the exact optimal solution. Our model identifies the optimal South Carolina plan at the minimum penalty of 64. Motivated by the 2019 lawsuit challenging the congressional plan as gerrymandering, we inspect the actual Maryland plan.

With the popularization of energy conservation and emission reduction, amounts of industrial production has taken energy conservation as a goal to achieve. The paper considers an online parallel-batch scheduling problem with deteriorating and incompatible families on identical machines to minimize the makespan, which minimizes the maximum energy consumption of machines. Specifically, the processing time of job $J_j$ is defined by an increasing function of its starting time $t$, i.e., $p_j={\alpha }_j(A+Bt)$, where ${\alpha }_j>0$ is the deterioration rate of job $J_j$. For the problem, we propose an online algorithm with a competitive ratio of $2+B{\alpha }_{max}$, where ${\alpha }_{max}$ is the largest deterioration rate in an instance. Furthermore, the paper presents a concise computational study of the numerical experiment to show that our algorithm performs very well in practice of this model.

In the production scheduling of prefabricated components, we study an online $m$ parallel-batch machines scheduling model considering learning effect jobs with $f$ incompatible job families to minimize the makespan in this paper, where the capacity of batch is unbounded. Job families indicate that a job must belong to some job family and jobs of distinct job families are incapable to be executed in the same batch. The information of each job including its basic processing time $b_j$ and release time $r_j$ is unknown in advance and is revealed at the instant of its arrival. Moreover, the actual processing time of job $J_j$ with learning effect is $p_j=b_j(a-bt)$, where $a$ and $b$ are non-negative parameters and $t$ denotes the starting time of prefabricated job $J_j$, respectively. When $m=f$, we propose an online algorithm with a competitive ratio of $2-b{b}_{min}$. Furthermore, the performance of the online algorithm is demonstrated by numerical experiments.

Over the past few years, graph contrastive learning (GCL) has gained great success in processing unlabeled graph-structured data, but most of the existing GCL methods are based on instance discrimination task which typically learns representations by minimizing the distance between two versions of the same instance. However, different from images, which are assumed to be independently and identically distributed, graphs present relational information among data instances, in which each instance is related to others by links. Furthermore, the relations are heterogeneous in many cases. The instance discrimination task cannot make full use of the relational information inherent in the graph-structured data. To solve the above-mentioned problems, this paper proposes a relation-aware graph contrastive learning method, called RGCL. Aiming to capture the most important heterogeneous relations in the graph, RGCL explicitly models the edges, and then pulls semantically similar pairs of edges together and pushes dissimilar ones apart with contrastive regularization. By exploiting the full potential of the relationship among nodes, RGCL overcomes the limitations of previous GCL methods based on instance discrimination. The experimental results demonstrate that the proposed method outperforms a series of graph contrastive learning frameworks on widely used benchmarks, which justifies the effectiveness of our work.

As a kind of generalization of Transformers in the graph domain, Global Graph Transformers are good at learning distant knowledge by directly doing information interactions on complete graphs, which differs from Local Graph Transformers interacting on the original structures. However, we find that most prior works focus only on graph-level tasks (e.g., graph classification) and few Graph Transformer models can effectively solve node-level tasks, especially semi-supervised node classification, which obviously has important practical significance due to the limitation and expensiveness of these node labels. In order to fill this gap, this paper first summarizes the theoretical advantages of Graph Transformers. And based on some exploring experiments, we give some discussions on the main cause of their poor practical performance in semi-supervised node classifications. Secondly, based on this analysis, we design a three-stage homogeneity augmentation framework and propose a Semi-Global Graph Transformer. Considering both global and local perspectives, the proposed model combines various technologies including self-distillation, pseudo-label filtering, pre-training and fine-tuning, and metric learning. Furthermore, it simultaneously enhances the structure and the optimization, improving its effectiveness, scalability, and generalizability. Finally, extensive experiments on seven public homogeneous and heterophilous graph benchmarks show that the proposed method can achieve competitive or much better results compared to many baseline models including state-of-the-arts.

This paper presents and discusses the implementation of a learning accelerator for an LSTM neural network that utilizes an FPGA. The accelerator consists of a backpropagation through time algorithm for an LSTM. The presented net performs a binary classification task and consists of an LSTM and a dense layer. The performance is then compared to both a hard-coded Python implementation and an implementation using Keras library and the GPU. The implementation is executed using the DSP blocks, available via the Vivado Design Suite, which is in compliance with the IEEE754 standard. The results of the simulation show that the FPGA implementation remains accurate and achieves higher speed than the other solutions.

Auto-scoping in OpenMP has been proposed as a means for relieving the programmer from the non-trivial effort of identifying the data sharing attributes of variables used within code regions that produce concurrency, such as parallel and task constructs. In this work we reconsider autoscoping on parallel constructs, including combined parallel-worksharing constructs. We first show that the current implementations do not always scope variables correctly in the presence of nested parallel constructs. We then proceed to extend the set of rules that guide the autoscoping decisions so as to handle nested constructs successfully. We also discuss how this functionality is implemented in the OMPi source-to-source OpenMP compiler.

An interconnection network can be modelled as a connected graph $G$. The reliability of interconnection networks is critical for multiprocessor systems. Several conditional edge-connectivities have been introduced in the past for accurately reflecting various realistic network situations, with the $h$-extra edge-connectivity being one such conditional edge-connectivity. The $h$-extra edge-connectivity of $G$, denoted by ${\lambda }_h(G)$, is the minimum cardinality of faulty edges whose deletion disconnects the graph $G$ with each resulting component containing at least $h$ processors. In general, for a connected graph $G$, determining whether the graph exists an $h$-extra edge-cut is $NP$-hard. The folded-crossed hypercube $FC{Q}_n$ is a variation of the crossed hypercube $C{Q}_n$ with $N=2^n$ processors. In this paper, after excavating the layer structure of folded-crossed hypercube, we investigate some recursive properties of ${\lambda }_h(FC{Q}_n)$, based on some recursive properties, an effective $O(log(N))$ algorithm of $h$-extra edge-connectivity of folded-crossed hypercube is designed, which can determine the exact value and the ${\lambda }_h$-optimality of ${\lambda }_h(FC{Q}_n)$ for each positive integer $1\le h\le 2^{n-1}$. Our results solve this problem thoroughly.

Directed cycles in digraphs are useful in embedding linear arrays and rings, and are suitable for designing simple algorithm with low communication costs in parallel computer systems, thus the existence of directed cycles on digraphs has been largely investigated. Let $n$, $k\ge 2$ be integers. Bermond et al. [Journal of Graph Theory 4(3) (1980) 337–341] proved that if the size of a strong digraph $D$ with order $n$ is at least $\left(\genfrac{}{}{0ex}{}{n-k+2}{2}\right)+k-1$, then the girth of $D$ is no more than $k$. Consequently, when $D$ is a 4-free strong digraph with order $n$, which means that every directed cycle in $D$ has length at least $5$, then the maximum size of $D$ is $\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+2$. In this paper, we mainly give the structural characterizations for all 4-free strong digraphs of order $n$ whose arc number exactly is $\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+2$.

In this work, we determine all the eigenvalues and their corresponding multiplicities of the normalized Laplacian matrix for folded hypercubes. Furthermore, we establish the explicit formula to calculate Kemeny’s constant for random walks on the folded hypercube, which indicates that its growth is roughly consistent with the network order. In addition, we also determine the number of spanning trees and degree-Kirchhoff index of folded hypercubes. Especially, we make some comparisons with that of hypercubes to verify that folded hypercubes have superior properties than hypercubes.