4. CASA Imager Memory Footprint

S. Bhatnagar, K. Golap and U. Rau
March 29, 2012

This note is under construction ! We are verifying correctness....

This memo attempts to generate expression(s) for the steady-state memory footprint of the CASA imager. By ``steady state'', we mean the combined memory required for one major- and one minor-cycle. The expressions for the total memory are also factored into seperate terms for major- and minor-cycle memory footprints. Note that while there is some analysis, this memo is primarily focused on describing the current memory footprint and not for describing the why of the footprint for various algorithms.

If you are not interested in the details, you can directly read Eqs. 4.4, 4.8, 4.15 and 4.16 for the memory footprint for classical Clean, MS-Clean, MS-MFS Clean and Mosaic Clean respectively. Memory footprint in units of number of N-pixel sized images for typical values of the associated parameters for classical Clean, MS Clean and MS-MFS Clean are given in Tables 4.1, 4.2 and 4.3 respectively.

The equations are parametrized by the size of the user-defined image ( $N_X \times N_Y$ ), number of visibility plane polarizations used ($N^{Vis}_P$ ) to generate the user-defined number of image-plane polarization planes ($N^{Img}_P$ ), number of user-defined scales ($N_S$ ) and Taylor-terms ($N_T$ ) for MS Clean, and MS-MFS Clean. Since the overheads are different for different classes of algorithms, the equations are also separated in three different classes:

1. Single-pointing classical ``Clean'' (non-MS, non-MS-MFS Clean)
2. Single-pointing MS Clean
3. Single-pointing MS-MFS Clean

4.1 Symbols Used

• fp: Unit used to represent floating-point pixels.

• $N = N_X \times N_Y$ : The number of pixels in the image each requiring floating-point storage (4 bytes).

• $N^{Vis}_P$ : The number of visibility-plane polarization products used.

• $N^{Img}_P$ : The number of polarization planes in the image.

• $N_S$ : The number of scales used in MS-Clean or MS-MFS Clean.

• $N_T$ : The number of Taylor terms used in MS-MFS.

4.2 Gridding/De-gridding

The constant overhead which is constant across all classes of algorithms consists of 3 scratch images, one mask-image and one complex image, each with $N^{Img}_P$ number of planes

$$I^{overhead}_o = I^{gS} + I^{ggS} + I^{work} + I^{Mask} + I^{cImage}$$

$$= N^{Img}_P \left[N + N + N + N + 2N\right] = 6 N N^{Img}_P {\tt\bf fp}$$ (4.1)

The computing cost of gridding/de-gridding scales with the number of visibility points and the convolution function support area. For large data-sets (which do not fit in the computer RAM), the run-time cost is dominated by data I/O.

To minimize this data I/O, CASA imager holds separate complex grids for forward and reverse transforms. Each pixel of one of these grids consumes single-precision complex storage, while the other has double precision complex storage. Each has $N^{Vis}_P$ number of polarization planes. The total storage for these grids is therefore

$$I^{Grid}_o = I^{Complex} + I^{DComplex}$$

$$= N^{Vis}_P \left[ 2 N + 2\times 2 N \right]$$

$$= 6 N N^{Vis}_P {\tt\bf fp}$$ (4.2)

4.2.1 Imaging

For the image-plane operations of Clean, we hold one FP-image each to represent the residual image $I^R$ , the PSF $I^{PSF}$ and the model image $I^C$ . Each has $N^{Img}_P$ number of polarization planes. Together the amount of memory they use is

$$I^{Img}_o = I^R_o + I^{PSF}_o + I^C_o +I^{Mask}_o$$

$$= N^{Img}_P \left[ N + N + N + N\right]$$

$$= 4N N^{Img}_P {\tt\bf fp}$$ (4.3)

4.3 Single Pointing non-MS non-MS-MFS Clean

The total memory foot print for single pointing non-MS, non-MFS-MFS Clean is the sum of Eqs. 4.1, 4.2 and 4.3.

$$M_{classical} = I^{Grid}_o + I^{Img}_o +I^{overhead}_o$$

$$= 8 N N^{Img}_P + 6 N N^{Vis}_P {\tt\bf fp}$$

$$= 4 N \left[ 8 N^{Img}_P + 6 N^{Vis}_P \right] {\tt \bf Bytes}$$ (4.4)

The major-cycle memory footprint is given by the first two terms and the minor-cycle memory footprint is given by the last term in the following expression:

$$MS_{classical} = N\left\{6N^{Vis}_P + 4N^{Img}_P\right\} + N\left\{4N^{Img}_P\right\} {\tt\bf fp}$$ (4.5)

Table 4.1: The number of N-pixel sized images required for typical settings for the classical Clean algorithm.

Stokes	$N^{Vis}_P$	$N^{Img}_P$	No. of N-pixel size images	Major-, Minor-Cycle breakup
I	1	1	14	10,4
IV	2	2	28	20,8
IQUV	4	4	56	40,16

4.4 Single Pointing MS Clean

$$I^{Img}_{MS} = I^{ImageSkyModel} + I^{overhead}_o$$

$$= I^{PSF} + I^R + I^{Models} + I^{\delta Model} + I^{overhead}_o$$

$$= N^{Img}_P \left[N + N + N + N\right]+ 6NN^{Img}_P$$

$$= 10NN^{Img}_P {\tt\bf fp}$$ (4.6)

In addition to the above, MS-Clean has an overhead of holding one image per scale $I^{iScale}$ , one mask-image per scale $I^{scaleMask}$ and a scratch image $I^{dirty*scale}$ . All these have $N^{Img}_P$ number of polarization planes. Further, complex images $I^{scaleXFR}$ per scale, $I^{XFR}$ and $I^{cWork}$ are also allocated. The MS-Clean code additionally also allocated the $I^{\delta Model}$ image with $N^{Img}_P$ polarization planes. The total memory footprint for this is:

$$I^{MatrixCleaner}_{MS} = I^{dirtycopy} + \left[ \frac{N_S(N_S+1)}{2} \right] I^{PSF}_{MS} ... ...eMask} + N_s I^{dirty*scale} + I^{mask}+ N_s I^{scaleXFR} + I^{XFR} + I^{cWork}$$

$$= N + \left[ \frac{N_S(N_S+1)}{2}N \right] + N_s \left[N+N+N\right]+N + 2\times \frac{N_s N}{2} + 2\times \frac{N}{2} + 2\times N$$

$$= \frac{N}{2}\left[N^2_s + 9 N_s + 10 \right]$$ (4.7)

In addition, storage for residual images per scale is also required. For the PSF images, the PSF corresponding to the cross-terms between scales is also computed. All these also have $N^{Img}_P$ number of polarization planes. The total memory required for MS-Clean is therefore

$$M_{MS} = I^{Grid} + I^{Img}_{MS} + I^{MatrixCleaner}_{MS}$$

$$= 6 N N^{Vis}_P + 10NN^{Img}+\frac{N}{2}\left[N^2_s + 9N_s + 10\right]$$

$$= \frac{N}{2}\left[12N^{Vis}_P+20N^{Img}_P+N^2_s+9N_s+10\right] {\tt\bf fp}$$

$$= 2N\left[12N^{Vis}_P+20N^{Img}_P+N^2_s+9N_s+10\right] {\tt\bf Bytes}$$ (4.8)

The major-cycle memory footprint is given by the first two terms and the minor-cycle memory footprint is given by the last term in the following expression:

$$M_{MS} = I^{MajorCycle} + I^{MinorCycle}$$

$$= \left\{I^{Grid}+I^{Img}_{MS}\right\} + I^{MatrixCleaner}_{MS}$$

$$= N\left\{6 N^{Vis}_P + 10N^{Img}\right\}+\frac{N}{2}\left\{N^2_s + 9N_s + 10\right\} {\tt\bf fp}$$ (4.9)

Table 4.2: The number of N-pixel sized images required for typical settings for the MS Clean algorithm.

Stokes	$N^{Vis}_P$	$N^{Img}_P$	$N_S$	No. of N-pixel size images	Major-, Minor-Cycle breakup
I	1	1	1,5,7	16, 42, 61	(10,6); (10,32); (10,51)
IV	2	2	1,5,7	31, 79, 115	(20,1); (20,59); (20,95)
IQUV	4	4	1,5,7	61, 153, 223	(40,21); (40,113); (40,183)

4.5 Single Pointing MS-MFS Clean

MS-MFS needs to account for the cross terms between scales and Taylor-terms. To account for the coupling between scales and Taylor terms, the number of images required for the MS-MFS Clean is

$$I^{Img}_{MSMFS} = I^{ImageSkyModel} + I^{overhead}_o$$

$$= I^{PSF} + I^R + I^{model}+I^{overhead}_o$$

$$= N^{Img}_P N_T \left[N + N + N\right]+6NN^{Img}_P$$

$$= 3N^{Img}_PN\left[N_T +2\right] {\tt\bf fp}$$ (4.10)

Additionally, MS-MFS also has the following storage overheads. Note that are $I^{dirtyXFR}$ , $I^{cWork}$ , $I^{vecScaleFT}$ , and $I^{vecPSFFT}$ are half-complex images.

$$I^{MTMatrixCleaner}_{MSMFS} = I^{PSF}_{MSMFS} + I^{scale} + I^{scalemask} + I^{work} + I^{modelcopy} + I^R + I^{coeff}+I^{mask}+$$

$$I^{dirtyXFR}+I^{cWork} +I^{vecScaleFT}+I^{vecPSFFT}$$ (4.11)

$$= N\frac{N_T(N_T+1)}{2} \frac{N_S(N_S+1)}{2} +$$

$$\left[ N_sN + N_s N + N_s N + N_T N + N_s N_T N + N_s N_T N \right]+N$$

$$+2\frac{N^{Img}_PN}{2}+2\frac{N^{Img}_PN}{2}+2\frac{N^{Img}_PN_SN}{2}+2\frac{(2N_T-1)N}{2}$$ (4.12)

$$= \frac{N}{4}\left\{N^2_T N^2_s+N^2_TN_s+N^2_SN_T+7N_sN_T + 20 N_T+12N_s+4N^{Img}_P\left(N_s+1\right)-4 \right\}$$ (4.13)

The total memory footprint for the single pointing MS-MFS Clean therefore is

$$M_{MSMFS} = I^{Grid}_{MSMFS} + I^{Img}_{MSMFS} + I^{MTMatrixCleaner}_{MSMFS}$$

$$= 6 N N^{Vis}_P N_T +$$

$$3N^{Img}_PN\left[N_T +2\right]+$$

$$\frac{N}{4}\left\{N^2_T N^2_s+N^2_TN_s+N^2_SN_T+7N_sN_T + 20 N_T+12N_s+4N^{Img}_P\left(N_s+1\right)-4 \right\}$$

$$= 3N\left\{N_T\left[2N^{Vis}_P+N^{Img}_P\right]+2N^{Img}_P\right\} +$$

$$\frac{N}{4}\left\{N^2_T N^2_s+N^2_TN_s+N^2_SN_T+7N_sN_T + 20 N_T+12N_s+4N^{Img}_P\left(N_s+1\right)-4 \right\} {\tt\bf fp}$$ (4.14)

$$= 12N\left\{N_T\left[2N^{Vis}_P+N^{Img}_P\right]+2N^{Img}_P\right\} +$$

$$N\left\{N^2_T N^2_s+N^2_TN_s+N^2_SN_T+7N_sN_T + 20 N_T+12N_s+4N^{Img}_P\left(N_s+1\right)-4 \right\} {\tt\bf Bytes}$$ (4.15)

Table 4.3: The number of N-pixel sized images required for typical settings for the MS-MFS algorithm.

Stokes	$N^{Vis}_P$	$N^{Img}_P$	$N_S$	$N_T$	No. of N-pixel size images	Major-, Minor-Cycle breakup
I	1	1	1,5,7	1	17.5, 53.5, 77.5	(6.11.5); (6,47.5); (6,71.5)
I	1	1	1,5,7	2	29.5, 101.5, 155.5	(12,17.5); (12,89.5); (12,143.5)
I	1	1	1,5,7	3	42.5, 164.5, 261.5	(18,24.5); (18,146.5); (18,243.5)
IV	2	2	1,5,7	1	35.0, 107.0, 155.0	(12,23); (12,95); (12,143)
IV	2	2	1,5,7	2	59.0, 203.0, 311.0	(24,35); (24,179); (24, 287)
IV	2	2	1,5,7	3	85.0, 329.0, 523.0	(36,49); (36, 293); (36, 487)
IQUV	4	4	1,5,7	1	70.0, 214.0, 310.0	(24,46); (24, 190); (24, 286)
IQUV	4	4	1,5,7	2	118.0, 406.0, 622.0	(48,70); (48, 358); (48, 574)
IQUV	4	4	1,5,7	3	170.0, 658.0, 1046.0	(72,98); (72,586); (72,974)

4.6 Multiple Pointing Mosaic

For mosaic imaging, an extra single-precision complex grid is allocated. Depending on the algorithm used (classical, MS-Only, MS-MFS), the memory footprint is

$$M_{Mosaic} = 4\times 2N + M_{Algo} {\tt\bf Bytes}$$ (4.16)

where $M_{Algo}$ can be $M_{classical}$ , $M_{MS}$ or $M_{MSMFS}$ .