I tried your code and did not use your
#define _SQR(a) ((a)*(a))
by replacing
DISTANCE = _SQR(xPos[particles1[idx]] - xPos[particles2[idy]])+ _SQR(yPos[particles1[idx]] - yPos[particles2[idy]])+ _SQR(zPos[particles1[idx]] - zPos[particles2[idy]]);
with this
DISTANCE = _SQR(xPos[particles1[idx]] - xPos[particles2[idy]])+
double x, y, z;
_SQR(yPos[particles1[idx]] - yPos[particles2[idy]])+
x = _SQR(xPos1[idx]zPos[particles1[idx]] - xPos2[i]zPos[particles2[idy]]);
with this
double x, y, z;
x = (xPos1[idx] - xPos2[i]);
y = (yPos1[idx] - yPos2[i]);
z = (zPos1[idx] - zPos2[i]);
DISTANCE = x*x + y*y + z*z;
the time came down from 2600ms to 1800ms for 22.5 billion points.