Gaia is a 5-year ESA (European Space Agency) cornerstone mission launched at the end of 2013. Its main goal is the production of a 5-parameter astrometric catalogue (i.e. positions, parallaxes and the two components of the proper motions) at the micro-arcsecond level for about 1 billion stars of our Galaxy by means of high-precision measurements. The main task of the code presented in this paper is the Gaia astrometric core solution, represented by a system of up to 72 billion linear observations equations and 600 million unknowns, resulting in a very large and sparse system matrix. This problem is solved by means of an ad-hoc implementation of the PC-LSQR iterative algorithm aimed at maximizing the number of adjustable stellar objects, which makes also use of a pre-conditioning technique consisting in a re-normalization of the columns of the system matrix to improve the convergence speed. After a description of the parallel algorithm, we present the results obtained on a IBM BlueGeneQ system using both the message-passing and OpenMP paradigms. We also report on the performances obtained from simulations of different stages of the mission from beginning to end.