Computação Paralela - Atividade 02

Leia com atenção as instruções abaixo.

Valor: 2,0 pontos na 1ª Nota.

Data da Entrega Limite: 16/04/2022

Formato de Entrega: envie um .pdf com a resolução, feito em meios digitais, para o chat privado do professor no Slack.

A atividade é individual.

Questão Única - 2,0 Pontos

Multiplicação de Matrizes utilizando uma máquima PRAM CREW. Sejam $A$ e $B$ $\in$ $R^{nxn}$ duas matrizes e $C = A * B $ seu produto dado em coordenadas:

\begin{equation} C_{ij} = \sum_{k=0}^{n-1}{A_{ik} * B_{kj}}\text{ para todo $i$ e $j \in$ } \{0, ..., n-1\} \end{equation}

Projete um algoritmo CREW que utilize $O(n^3)$ processadores e $O(n^3)$ espaço em memória para calcular $ C$ em tempo logarítmico.

Informe o pseudocódigo que é necessário para calcular o resultado quando $n$ é potência de 2.
Dê uma solução simples caso $n$ não seja uma potência de 2. A complexidade é afetada?
Sua solução é ótima em custo? (A equação do custo é linear?) Se não, forneça uma solução com custo ótimo.