O Porte de RE2 ficou muito famoso pela proeza de compressão de video e audio da Angel Studios, mas o estúdio alemão Factor 5 conseguiu uma proeza também no console, uma tarefa se não mais impossível ainda que RE2 não pelo audio ou que o jogo tenha tido FMVs mas sim pelo jogo ter sido portado do PC, ter uma enorme quantidade de texturas e um minímo de processamento e memoria muito , muito mais alto do que as especificações do Nintendo 64, o jogo também era 2 discos e pior ainda o espaço disponivel para a Factor 5 foi a metade do cartucho do RE2
Visualizar anexo 199431
Olhando as configurações minimas vemos que o jogo requer o dobro de processamento em relação ao N64
32mb de RAM fora 4mb de memoria somente de vídeo dedicado com suporte ao directx 6.1 ,e essa versão da epoca ocupava mais de 800mb no hd , 700 animações diferentes para cada personagem, mais de 50 minutos de audio, estamos vendo um jogo aqui que seria mais viavel ser portado direto para a sexta geração de consoles , ao contrario de RE2 que o consumo de memoria era menor pois o PS1 possuia menos memoria que o N64. Agora vamos tentar entender como a Factor 5 conseguiu recodificar esse jogo no N64 adicionando mais conteudos e até detalhes nos gráficos bem como melhorias no gameplay e som Surround como era de costume
- Baseado em Indiana Jones e a Infernal Machine para PC
- Chicoteie, salte, escale, rasteje e nade em incríveis ambientes 3D
- Sobreviva ao desafio de criaturas famintas, robôs hostis, monstros estranhos, metade do Exército Vermelho e muito mais (incluindo ¿oh não ¿cobras!)
- Descubra 17 capítulos de uma história emocionante e cheia de ação
- Viaje pelo mundo para locais exóticos, das ruínas da Babilônia aos labirintos dos reis núbios
- Todas as armas de que você precisa, incluindo pistolas automáticas, metralhadoras, granadas, cargas de mochila, bazucas e, é claro, o confiável chicote e revólver de Indy
- Motor completamente recodificado pela LucasArts e Factor 5 para desempenho máximo no N64
- Suporte para pacote de expansão de 4 MB ¿o jogo é executado em modo de alta resolução
- Novo sistema de controle corrige o movimento desajeitado e desajeitado da versão para PC
- Novos efeitos de iluminação, efeitos de partículas e transparências de água adicionam ainda mais realismo a um título já realista.
- Muita fala no jogo e som surround brilhante usando as técnicas de compressão de marca registrada do Factor 5.
Uma equipe de apenas 8 pessoas, 19 meses de produção
Visualizar anexo 199480
A grande força era o cartucho N64. Usamos o cartucho quase como a RAM normal e transmitimos todos os níveis de dados, texturas, animações, música, som e até mesmo código de programa enquanto o jogo está rodando. Com o tamanho final dos níveis e a quantidade de texturas, a RAM do N64 nunca teria sido nem remotamente suficiente para caber em qualquer nível individual. Portanto, a tecnologia do cartucho realmente salvou o dia.
Limitações da taxa de preenchimento do N64 foram contornadas . Implementado modo Hi-Res no Rogue por causa de sua aparência nítida, mas a taxa de quadros era questionável. Assim, ao ligar os motores de Indy e Naboo, o objetivo principal era obter uma alta taxa de quadros em Hi-Res. Isso significava não usar o Z-Buffer, porque ele sozinho usa um pouco da taxa de preenchimento do N64.
Todos os truques possíveis em termos de uso ideal do cache de textura 4K para cada textura. Os programadores descobriram os formatos de textura mais estranhos para obter a resolução máxima de cada textura. Uma ferramenta elaborada analisa cada textura original e tenta encontrar o melhor formato de textura para ela no N64. A ferramenta também permite manipular e escolher esses formatos de textura manualmente, algo que tivemos que fazer em muitos casos.
Introdução
A tarefa de portar
Indiana Jones e a Infernal Machine do PC para o N64 provou ser bastante desafiadora. O Nintendo 64 conseguia lidar com a quantidade de polígonos muito bem, mas o uso de memória era um grande problema porque os desenvolvedores do PC original não precisaram se preocupar com isso. Enquanto uma quantidade de memória típica de PC pode ser de 128 MB, o N64 precisava rodar o jogo com apenas 4 MB - e isso também deve conter o código, buffers de quadro, texturas e listas de exibição. Você pode aproveitar as vantagens do N64 Expansion Pak para fornecer maior resolução e melhor desempenho, mas apenas se estiver presente.
Olhando apenas para esses números, parece que esse tipo de desafio está fadado ao fracasso desde o início. No entanto, quando o projeto começou, o jogo original para PC era muito menor em termos de textura e uso do modelo. Como todos sabemos, os projetos tendem a crescer durante a última fase de produção porque todos querem que o jogo seja o melhor possível. Certamente, um jogo de aventura como
Indy forneceu oportunidades suficientes para crescimento.
Descobrimos que estávamos procurando por cada mil bytes que poderíamos liberar no final. Vários métodos diferentes foram usados para torná-lo adequado. Este artigo apresenta um resumo dos métodos mais importantes necessários para lidar com as restrições de memória, muitos dos quais são aplicáveis e benéficos para outros projetos. Reduzir o uso de memória também ajuda a aumentar o desempenho porque os dados são mais provavelmente locais e, portanto, mais prováveis de serem encontrados em um dos caches de dados da CPU.
Pode-se argumentar que os desenvolvedores hoje não precisam mais se concentrar em problemas de restrição de memória por causa de novos sistemas como o Sony Playstation 2 e o Nintendo Gamecube. No entanto, embora seus recursos de renderização tenham melhorado continuamente, seus subsistemas de memória não mudaram muito. Isso sugere que a organização da memória e o uso eficiente da memória são agora um problema ainda mais urgente.
Cenário
A abordagem usada para portar
Indy para o N64 compartilha muitas semelhanças com um caminho de dados que é usado na produção de um título original do zero. Normalmente, os dados de arte e nível são exportados para o formato de dados específico do mecanismo de jogo usando uma combinação de ferramentas de exportação. Esses, por sua vez, são ligados, criando um recurso binário que é carregado no destino. Para reduzir o tamanho do recurso binário, ficamos com duas opções: reescrever a ferramenta de exportação configurando-a para gerar estruturas menores e mais otimizadas ou usar a inicialização do jogo para PC existente e a parte de inicialização para carregar o recurso binário.
Escolhemos a segunda abordagem, porque oferecia o benefício de uma inicialização rápida, visto que todos os dados de carregamento e inicialização do código já estavam no lugar. Tudo o que precisávamos fazer era pegar o jogo e remover o loop de renderização dele. A partir daqui, poderíamos pegar todas as estruturas de dados do jogo, reescrevê-las e otimizá-las de maneira fácil (Figura 1). Nós nos familiarizamos com a estrutura interna do jogo no processo. Chamamos esse executável abusado de munger. Nós o estendemos para otimizar e reescrever todas as estruturas de dados. Também fornecia mais verificações de consistência, que eram necessárias para garantir que nossas alterações nas estruturas de dados não prejudicassem os dados convertendo valores de 32 bits em oito bits.
Esta abordagem tem muitas semelhanças entre um caminho de dados original porque é usado para um título original e, portanto, os métodos usados e as lições aprendidas ao portar
Indy se aplicam aos títulos originais. Também é importante levar em consideração os requisitos de gerenciamento e armazenamento de dados, uma vez que a quantidade de dados de arte (por exemplo, geometria, texturas, dados de animação, etc.) está aumentando com o lançamento dos sistemas de próxima geração
Métodos Usados
Os métodos usados são categorizados em três classes. O restante do artigo discute os métodos em mais detalhes e oferece algumas dicas práticas, que podem ser úteis para aqueles que estão enfrentando problemas de memória semelhantes.
- Reescrevendo e otimizando estruturas de dados: diminuir o tamanho das estruturas de dados parece um processo tedioso e errôneo; bem feito, isso pode ser uma maneira fácil de reduzir o tamanho dos dados.
- Cache de recursos no destino: embora uma grande quantidade de dados possa ser armazenada em cache (isso funciona surpreendentemente bem), diferentes tipos de dados requerem diferentes abordagens de cache. Os esquemas de cache usados são descritos e classificados.
- Usando um Kernel de Memória Virtual para reduzir o tamanho do código: um dos benefícios da programação do console é que você tem controle total sobre o hardware de destino. A implementação de um kernel de memória virtual parece exagero no início, no entanto, não apenas fornece memória preciosa, mas também ajuda no desenvolvimento e na depuração. Em geral, um kernel de memória virtual apresenta um meio de interceptar o acesso ilegal à memória.
Método A: Reescrevendo e Otimizando Estruturas de Dados
Um problema básico no início do projeto era que os dados do PC estavam todos em little-endian, enquanto o N64 (e GCN) usa big-endian. Embora seja possível alterar o endianess da CPU MIPS4300i, seria necessário um novo sistema operacional, o que não era viável na época. Uma vez que os dados tiveram que ser trocados de acordo com o tamanho da palavra dos dados (ou seja, você troca um valor de 32 bits de uma maneira diferente do que troca um valor de 16 bits e você não troca um byte), o munger precisava saber o layout das estruturas de dados. Isso foi necessário porque é fácil escrever um array. Os vetores de ponto flutuante são um ótimo exemplo. Você sabe que um vetor consiste em três valores de ponto flutuante consecutivos, cada um com 32 bits. A partir disso, você pode derivar um pequeno trecho de código, que trocaria "
Esse problema é ainda mais desafiador se você precisar escrever estruturas complexas, que contêm subestruturas e subuniões. Você teria que escrever um pequeno pedaço de código para cada definição de tipo no jogo, o que seria quase impossível de manter porque uma discrepância entre a definição de tipo e o pequeno pedaço de código faria com que os dados fossem escritos incorretamente. Olhando para um jogo em grande escala, percebemos rapidamente que essa abordagem não era possível; simplesmente havia muitos tipos de dados envolvidos e muitos deles estavam sujeitos a mudanças constantes porque nosso objetivo era reduzir seu tamanho. Portanto, precisávamos de um mecanismo que pudesse determinar automaticamente como converter o endianess de estruturas de dados arbitrárias, independentemente de conterem uniões e subestruturas.
A solução parece um pouco assustadora no início, mas provou ser bastante útil. Durante a inicialização do munger, ele analisa uma parte de seu próprio código-fonte para determinar o layout de memória de todas as estruturas de dados que estão prestes a ser convertidas de big para little-endian. Com
Indy , isso teria sido muito difícil se permitíssemos a sintaxe C completa para estruturas de dados, incluindo arquivos e expansão de macro. Havia, no entanto, uma solução fácil que permitiu manter a análise realmente simples ao criar todas as estruturas C:
- Definição de um conjunto simples de macros do pré-processador C (Figura 2), que são fáceis de reconhecer por um scanner de linha única, mas se expandem para a sintaxe C válida.
- Usando um retorno de chamada durante o tempo de execução para especificar qual parte de uma união escrever, fornecendo um ponteiro (void *) para o objeto atual em questão.
- Manter todas as estruturas de dados a serem convertidas, juntas em um arquivo.
Fazendo isso, podemos modificar as estruturas de dados sem nos preocupar com quaisquer problemas de conversão. Também é um método viável para garantir o alinhamento adequado nos tipos de dados, pois é possível verificar todos os elementos de uma estrutura quanto à sua posição dentro dela. Seria necessário verificar se o compilador C não introduz preenchimento automático que é invisível para o munger. Isso pode ser feito usando algumas instruções #pragma específicas do compilador.
Visualizar anexo 199440
O exemplo acima se assemelha ao código C legal, que pode ser executado em qualquer compilador. Observe que nas definições da estrutura, cada linha ENTRY consiste em quatro elementos. Os dois últimos elementos são para uso do compilador e são substituídos pela macro #define ENTRY. O Munger do lado oposto examina o arquivo linha por linha e detecta as três palavras-chave BEGIN_STRUCT, ENTRY e END após remover o espaço em branco. Em seguida, analisa os primeiros dois elementos da linha ENTRY. O primeiro número fornece as informações de quantidade, enquanto o segundo campo declara o tipo de dados. O segundo campo não pode conter todos os tipos C. Ele só pode conter tipos C conhecidos pelo Munger, como UBYTE, UWORD, ULONG, float, enum e POINTER. Você também pode especificar tipos complexos, que já são conhecidos pelo Munger,
Usando mais algumas macros, subuniões e subestruturas podem ser especificadas. O Munger também reúne uma lista nomeada de todos os elementos e tipos envolvidos, portanto, é possível nomear elementos de estrutura durante o tempo de execução. Isso é útil quando é necessário decidir qual parte de um sindicato precisa ser escrita. Usando uniões, podemos interpretar um pedaço de memória de maneiras diferentes, o que afetará a troca de bytes durante a escrita. No entanto, cada objeto que está usando sindicatos deve codificar parte desse sindicato que está sendo usado. O uso de um retorno de chamada, que fornece o nome da estrutura / união em questão e um ponteiro para ela, permite que o Munger examine um objeto e retorne o nome correto da união para ser gravado no disco (Figura 3).
Visualizar anexo 199442
Como você pode economizar memória com isso?
Por que, você pode perguntar, é necessário ter uma discussão tão prolixa sobre como escrever estruturas de dados, quando tudo o que estamos tentando fazer é reduzir seu tamanho? A resposta é direta. Seu objetivo principal é reduzir o tamanho das estruturas de dados. Sendo assim, é óbvio que as próprias definições da estrutura de dados estão em constante mudança durante o processo de desenvolvimento. Lidar automaticamente com essas mudanças ajuda muito. No entanto, e se você alterar uma estrutura a ponto de exigir grandes mudanças no código do Munger, que, como lembramos, é baseado no código do jogo real? Por exemplo, se você alterar todos os pontos mundiais para um número inteiro de vetores de 16 bits em vez de flutuantes, você terminará com uma quantidade inacreditável de erros do compilador. Mesmo que esteja compilando, é muito duvidoso que o executável ainda funcione.
Portanto, apresentamos dois conjuntos de estruturas de dados. Deixe o conjunto original (conjunto A) como estava no jogo original para PC e no Munger. Também introduzimos um novo conjunto de estruturas de dados, que é, no início, idêntico ao conjunto A. Este conjunto (conjunto B) é reconhecido pelo munger como o conjunto que deve ser convertido em big endian e as definições dos dados as estruturas são lidas durante o tempo de execução, conforme descrito acima. As estruturas de dados no conjunto B são provavelmente menores do que as originais, usando técnicas diferentes, que são descritas mais tarde. Uma função de transferência também é necessária, que copia os dados do conjunto A para o conjunto B. Durante esta etapa de cópia, várias coisas podem ser feitas nos dados para remover a redundância e compactá-los. A máquina de destino (o N64 em nosso caso) só conhece os dados no conjunto B. Portanto, ele '
A otimização do conjunto B de estruturas de dados usa alguns princípios, que são resumidos aqui:
- Use tipos mais curtos do mesmo tipo (ou seja, use WORD em vez de LONG, use BYTE em vez de SHORT)
- Combine vários campos de bits, enumerações em um
- Use números inteiros curtos em vez de valores de ponto flutuante
- Remova e otimize o preenchimento dentro da estrutura
- Remova os componentes não utilizados
Obviamente, muitos desses métodos são perigosos porque os valores podem exceder as capacidades de seus tipos de dados. Além disso, usando números inteiros curtos para valores de ponto flutuante, podemos perder a precisão necessária. No entanto, se usarmos uma função de transferência para copiar os dados, é possível proteger contra todas essas armadilhas (na verdade, é loucura não fazer isso). Ao copiar um longo para um curto, simplesmente adicione uma instrução if e salve se o longo for <-32768 || > 32767. A mesma técnica pode ser usada para todos os outros problemas.
Mais técnicas
Além de alterar as próprias estruturas de dados, há várias outras técnicas que podem produzir quantidades consideráveis de memória.
- Encontre elementos exclusivos em grandes matrizes e use índices para acessá-los. Por exemplo, em vez de armazenar centenas de vetores de ponto flutuante, que estão todos apontando na mesma direção, apenas armazene um vetor e use um índice curto que procura o normal correto. Essa abordagem é viável para muitos dados, como normais, vértices e cores.
- Remova os dados redundantes herdados. Por exemplo, em um mecanismo de portal, sempre existem dois portais, onde um é o espelho exato do outro. Em Indy , foi possível cortar exatamente a metade das estruturas do portal, introduzindo uma broca "é-espelho". O código precisou ser alterado para inverter o normal do portal. Isso ganhou muita memória, pois a estrutura do portal era de tamanho considerável.
- Um mecanismo às vezes abusa das estruturas de dados. Tipos complexos são usados para representar tipos simples. O melhor exemplo em Indy foi o uso de uma estrutura de "coisa" para representar pontos no mundo 3D. O desperdício foi de cerca de 500 bytes para cada instância, o que totalizou quase 100k em um nível típico. A razão para essa má decisão de design no PC era que simplesmente não importava e os designers de níveis podiam usar as ferramentas de posicionamento de "coisas" no editor de níveis para especificar as posições. No entanto, foram necessárias algumas investigações e alterações no código do jogo, mas o esforço valeu a pena.
- Use campos de bits em vez de matrizes de booleanos. Às vezes, os booleanos são definidos como valores de 32 bits para contornar algumas armadilhas C típicas. No entanto, mesmo quando eles já são caracteres não assinados, você pode reduzir o tamanho para 1/8. Isso foi usado em Indy para reduzir o tamanho das informações de visibilidade potencial (PVS).
- Dê uma olhada na representação binária de objetos de dados. Algum esquema de compactação simples pode ser aplicado, especialmente quando os dados não são usados com freqüência. Pode ser benéfico usar um pequeno cache para ocultar os custos de descompressão (veja abaixo).
- Livre-se da precisão não utilizada e / ou desnecessária onde for viável. O sistema de animação de Indy no PC usava três flutuações de dados translacionais e três flutuações de dados rotacionais por quadro-chave. Ele também armazenou outros três flutuadores de informação delta translacional, uma vez que armazenou três flutuadores adicionais de informação delta rotacional mais um flutuante para o índice de tempo do quadro-chave (quadro #). Ao usar informações de rotação absoluta, os seis flutuadores para a informação delta podem ser removidos e, em vez de usar flutuadores para os seis valores restantes, usamos valores de 16 bits com sinal (na verdade, apenas 13 bits foram usados, os 3 * 3 bits restantes foram usados para codificar o número do quadro). Portanto, o tamanho de um quadro-chave foi reduzido de 7 * 4 = 28 bytes para 3 * 2 = 6 bytes.
No entanto, é preciso ter cuidado ao remover a precisão. Em
Indy , também convertemos vértices mundiais e normais mundiais de valores flutuantes para valores de 16 bits com sinal. O que aconteceu é que os ventiladores de triângulo ficaram esburacados e o sistema de colisão falhou porque assumiu polígonos convexos. Ao mover os vértices (ou seja, encaixá-los na grade inteira), essa propriedade foi perdida junto com a colisão para lidar com polígonos côncavos. Não há necessidade de mencionar que fizemos isso em
Indy .
- Encontre linhas correspondentes em enormes matrizes multidimensionais e armazene índices em referências. Observe que isso só funciona com dados somente leitura, uma vez que a modificação de um elemento pode afetar muitos elementos lógicos (Figura 4). Usar este método para compactar as tabelas de descrição de animação (qual animação tocar, para qual movimento, com qual velocidade, etc) ganhou quase 100k em Indy quando havia muita animação em um nível.
- Combine vários elementos de uma estrutura em uma união se eles forem mutuamente exclusivos. Essa técnica é mais do tipo 'último recurso' porque não se pode determinar rapidamente se alguns elementos de uma estrutura são realmente mutuamente exclusivos. Além disso, requer muitas mudanças de código para acessar os sindicatos corretamente.
- 'Terceirizar' subestruturas enormes se raramente forem usadas. Um bom exemplo disso são as estruturas de 'superfície' em Indy porque elas continham uma quantidade bastante grande de informações sobre propriedades de superfície, como animação e iluminação, que eram usadas apenas para superfícies de 'efeitos especiais'. Por sua própria natureza, havia menos de um por cento daqueles em um nível típico. Remova as informações de "fx especial" e armazene-as em um novo tipo de dados, como tSurfaceFX, e atribua um identificador (pode ser apenas um valor de oito bits). Durante o tempo de execução, aloque um novo tSurfaceFX assim que o mecanismo animar uma superfície.
Visualizar anexo 199443
Cache de recursos no destino
O armazenamento de objetos é baseado nas observações feitas durante qualquer ponto do jogo; você não precisa de todos os recursos de uma vez. Existem muitos tipos diferentes de recursos que você deve considerar armazenar em cache. Muitos recursos parecem difíceis de lidar ou não vale a pena armazenar em cache, uma vez que você assume que um cache não seria benéfico. Quando estávamos criando
Indy , as seguintes lições foram aprendidas:
- É difícil prever o desempenho de um cache. Geralmente, ele sempre tende a funcionar melhor do que o esperado, o que é obviamente uma coisa muito boa.
- Ao escrever um cache, torne-o geral. Não crie um cache, que lida com as texturas do mundo, é melhor criar um, que lida com todas as texturas.
Quando se trata de selecionar quais recursos armazenar em cache, você pode querer considerar tudo, dependendo de quão desesperado você está. Para dar uma impressão do que é viável, aqui está uma lista de coisas que foram armazenadas em cache com sucesso em
Indy no N64.
Texturas
Isso provou ser muito benéfico porque você raramente vê todas as texturas de uma vez em um ambiente interno típico. As texturas são freqüentemente compactadas usando um método LZ.
Listas de exibição para geometria de mundo / objeto
As listas de exibição são um grande problema de memória no N64. Eles contêm informações binárias usadas pelo hardware de renderização para desenhar primitivas e são consideravelmente maiores do que a própria geometria. Por esse motivo, a geometria do mundo (dividida em setores) e os objetos são convertidos de sua representação geométrica para exibir listas quando se tornam visíveis. Eles são eliminados se não forem processados por um período de tempo específico.
Potencialmente Informações de Visibilidade (PVS)
Para acelerar a renderização, uma tabela pvs é usada para facilitar o cálculo da visibilidade. No entanto, ele contém um campo de bits para cada setor mundial, que é do tamanho "# setores mundiais". Um bit definido neste campo de bits significa que há uma linha de visão entre um par de setores. O renderizador só precisa das informações de visibilidade para o setor em que a câmera está atualmente. Isso significa que o conjunto de PVs raramente muda (ou seja, se o jogador estiver correndo rápido, a cada cinco segundos). Mesmo se estiver mudando, é provável que a câmera volte para um setor visitado anteriormente (ou seja, o jogador está correndo em círculos). Portanto, um cache com apenas dez entradas ajuda muito. Como adicionar um novo conjunto de PVs ao cache é um evento raro, os dados são baixados da ROM e descompactados usando um método RLL.
Dados de animação
Em um jogo baseado em personagem de terceira pessoa, há muitas trilhas de animação que podem ser aplicadas aos personagens. Para cada ator, existem mais de 700 animações diferentes. Claro, alguns deles são usados apenas uma vez no jogo completo (ou seja, para cenas especiais). Seria um crime mantê-los todos na memória ao mesmo tempo. Felizmente, o sistema de animação usado no jogo original para PC fornecia funções para iniciar e parar uma trilha. Esses dois pontos tornaram fácil ancorar as funções de bloqueio e desbloqueio do cache.
Código de script
O mecanismo de script do jogo usava um código de bytes que foi interpretado para executar ações de script. Esses scripts eram específicos para uma determinada situação e nível. Portanto, armazená-los em cache foi uma ideia simples. Além disso, muitos scripts usavam um esquema básico de execução: após se inicializarem, eles esperavam que alguma condição específica ocorresse. Durante esse tempo, nenhum script é executado, então o código não precisa ficar parado.
Dados de colisão para geometria de mundo / objeto
Por sua própria natureza, as colisões ocorrem localmente. Os dados envolvidos consistem em normais e vértices. Se um objeto não está se movendo, o motor não realiza nenhuma verificação de colisão, portanto, seus normais e vértices não são necessários. Lembre-se de que, com a arquitetura N64, uma cópia desses 'pausas' nas listas de exibição para renderização. Infelizmente, não é possível acessar as listas de exibição para buscar vértices e normais porque o formato é binário, o que é extremamente complicado de acessar.
Modelos de objetos
Durante o jogo, muitos objetos são criados dinamicamente. Os objetos são criados a partir de um modelo que descreve as propriedades do novo objeto. Os modelos, portanto, não são constantemente necessários, com um cache de apenas oito sendo suficiente.
Benefícios do armazenamento em cache
O cache é usado para reduzir o uso de memória para um determinado conjunto de objetos. Isso é arquivado mantendo apenas uma quantidade fixa de objetos na memória. Quando precisar de espaço para um novo, você descobrirá qual deles não será usado por um tempo e o removerá, ao fazer isso você criará espaço para o novo objeto. Claro que o lixo ocorrerá quando você tornar o cache muito pequeno. Trashing é um termo usado para descrever uma linha de cache que é constantemente recarregada com diferentes objetos. Isso é ruim para o desempenho geral porque você está constantemente carregando e baixando do armazenamento em massa.
No entanto, há uma visão diferente sobre isso também. Sem o cache, você simplesmente precisa de uma quantidade específica de memória; não há nada para mexer. Quando você armazena um recurso em cache, existe a possibilidade de contrabalançar o desempenho em relação ao uso da memória. Talvez você esteja correndo tão apertado que fique feliz em oferecer um pouco de desempenho em troca de alguma memória tão necessária.
Com o cache, o uso de memória durante o tempo de execução pode ser corrigido. Ao criar objetos dinâmicos usando um cache, você pode impor um limite superior (é claro, deve estar tudo bem para descartar objetos antigos e recriá-los mais tarde). É uma idéia muito boa ter consertado as pegadas de memória nos consoles. No entanto, você deve fornecer modos de 'pânico' para alguns caches. Por exemplo, quando você usa um cache para renderizar a geometria e o cache está cheio, evitando, assim, que você limpe um elemento do cache (uma vez que todos eles estão visíveis), o renderizador lida com isso não renderizando o objeto. Caso contrário, você deve preencher a tela com sabedoria.
Outro benefício dos caches é que eles podem ocultar custos de acesso caros (na verdade, é para isso que servem os caches nas CPUs). Quando seus dados de origem de baixa entropia estão compactando bem, mas a descompactação está consumindo um pouco de tempo, é aconselhável colocar os objetos descompactados em um cache. Portanto, da próxima vez que forem solicitados, basta retornar um ponteiro para o objeto. Normalmente, um pequeno é suficiente para esse tipo de cache.
Esquemas de Cache
Existem basicamente duas abordagens diferentes para integrar um cache com seu cliente. Pode-se usar um Lock (); e desbloquear (); protocolo. Sempre que o motor decidir usar um objeto por um período de tempo prolongado, ele deve usar Lock (); com o cache primeiro. O cache, por sua vez, faz o que for necessário para fornecer esse recurso (ou seja, baixando e / ou descompactando). O objeto então reside no cache até que o cliente decida que não é mais necessário e emita uma chamada de desbloqueio. O cache reconhece isso e pode reutilizar a linha do cache para outros objetos. Obviamente, seria aconselhável manter as informações no cache, mesmo que ele não esteja mais bloqueado. As informações podem ser solicitadas novamente em breve e, desde que o cache não fique sem espaço. A desvantagem de usar este esquema é que é possível que o cache fique sem espaço, porque todas as linhas do cache são preenchidas com objetos. Uma vez que o Lock (); call retorna um ponteiro para o cliente, e o cliente pode usá-lo contanto que o ponteiro não tenha sido desbloqueado, não há como liberar uma linha de cache. Portanto, o cliente deve ser capaz de lidar com a condição "não".
A segunda abordagem para fazer a interface do cache com seu cliente é usar um Touch (); chamar o cache sempre que um objeto estiver prestes a ser usado. A ideia é que o ponteiro do objeto, retornado pelo Touch (); chamada, só é válida até o próximo toque (); ligar. Considerando a condição completa, a pior coisa que pode acontecer é ter o cache sendo constantemente recarregado e descartado. Isso causaria um desempenho ruim, mas pelo menos não há nenhuma condição especial com a qual se preocupar. Este é definitivamente o caminho a seguir se o cache for grande o suficiente e pode-se garantir que não haverá lixo. No entanto, sempre que um objeto é usado, deve haver um Touch (); chamada feita. Considere o Lock (); e desbloquear (); interface para reduzir a quantidade de sobrecarga se isso acontecer com frequência.
O método de escolha é baseado em uma série de circunstâncias diferentes, incluindo custo de fornecimento de recursos (tempo de download, tempo de descompactação), estrutura de software existente e a frequência de duração dos objetos em cache que estão sendo usados.
Cache de exemplo
O arquivo de cabeçalho de exemplo abaixo (cf. fig. 5) mostra as definições estruturais para o cache de vértices de
Indy . Este cache contém informações de vértices para propósitos de colisão com a geometria do mundo. É invocado sempre que ocorre uma colisão em um setor específico do mundo. Falando mais precisamente, ele contém uma matriz de valores de 16 bits sem sinal, que são índices na (um, grande) array de vértices mundiais. Os índices não ficam na memória o tempo todo, pois são usados apenas para fins de colisão.
A definição do cache consiste em três funções e uma definição de tipo. A estrutura contém um bit de alocação para cada uma das linhas de cache NUM_LINES (aqui: 128). Observe o uso das macros do pré-processador. Teria sido possível alterar o tamanho do cache dinamicamente durante o tempo de execução, no entanto, não há necessidade real disso, considerando que a definição de tamanho usando uma macro torna o código mais rápido para escrever. Além disso, o cache contém um mapeamento de uma linha de cache para um setor. Isso pode ser usado para encontrar rapidamente qual setor está armazenado em cache em uma linha de cache específica. Em contraste, há também um mapeamento de um determinado setor para uma linha de cache. Isso é usado quando o cache é solicitado a fornecer informações sobre um setor específico. Isso significa que o objeto não é armazenado em cache se o mapeamento não for inicializado (ou seja, 0xff). Se houver uma linha de cache atribuída, a posição dos dados é pesquisada usando o mapeamento CacheLine2Base [] com o endereço base do cache * Data. Uma vez que a quantidade de índices de vértice pode variar de setor para setor, a quantidade é codificada em CacheLine2Size [] também. O bloco de dados do cache é gerenciado usando um serviço freelist, que é encapsulado no membro tFreeList. Ele fornece alocação e desalocação básicas para a * área de dados. O cache rastreia a linha de cache mais antiga usando outro serviço. Este serviço tLRU (última utilização) fornece meios para manter uma lista ordenada por idade de acesso. Cada vez que o cache é acessado usando GetSectorPoints (); função, o LRU do cache é atualizado. Sempre que é hora de limpar uma entrada, o serviço LRU fornece a linha de cache mais antiga. É uma boa ideia implementar serviços separados, como tFreeList e tLRU,
Visualizar anexo 199446
O cache também contém um contador para controlar a quantidade de bytes baixados da ROM por motivos de depuração e criação de perfil. Pode-se notar também que embora o número de linhas de cache seja definido durante o tempo de compilação, o tamanho real do cache (ou seja, a quantidade de índices que ele pode conter com esse número fixo de linhas de cache) é dinamicamente ajustável usando o Initialize ( ); ligar. A quantidade de memória alocada para * Dados é alterada de acordo.
Detalhes de Implementação
Pode-se observar uma série de características para caches específicos com requisitos específicos, por meio da implementação de muitos caches diferentes. Algumas características têm um grande impacto no design de um cache.
Como o cache lida com a condição de "cheio"?
Existem diferentes abordagens para a condição "plena". Obviamente, o cache deve ter o tamanho adequado para que essa condição desagradável ocorra com pouca frequência. Você pode evitar isso executando as seguintes etapas:
- Descarte uma linha de cache aleatória. É claro que essa não é a maneira ideal de lidar com a situação; no entanto, é fácil de implementar. Isso é exatamente o que a unidade de gerenciamento de memória das CPUs MIPS faz, quando precisa buscar um novo descritor de página (veja abaixo).
- Descarte a linha de cache mais antiga. Isso só é útil quando há uma linha de cache desbloqueada (que é a mais antiga). Usando o Bloqueio (); e desbloquear (); protocolo nem sempre é o melhor método porque todas as linhas de cache podem estar bloqueadas no momento.
- Às vezes, é impossível descartar qualquer linha de cache (retornar NULL). Isso pode acontecer em um cache de textura, onde todas as linhas de cache contêm texturas bloqueadas porque o motor afirma que todas elas são visíveis. Em Indy , o renderizador desenhou um retângulo preenchido usando a cor ambiente do setor.
Qual é a frequência de acesso do cache?
Os caches variam em sua frequência de acesso. Às vezes, um objeto é solicitado apenas uma vez durante a inicialização do nível (ou seja, um objeto de script de inicialização) e nunca mais tocado. Às vezes, um objeto é usado com frequência durante um período de tempo prolongado em um nível específico, mas não é usado em nenhum outro lugar do jogo. Finalmente, alguns objetos (como os dados de animação dos personagens principais) são usados em todo o jogo de forma constante.
Também existe a frequência de acesso durante um único loop de renderização. O objeto é solicitado do cache para cada quadro ou é solicitado (bloqueado) apenas uma vez e então usado até ser liberado (desbloqueado) novamente? Os caches, que têm uma frequência de acesso baixa, se qualificam para dados de origem compactados porque a descompactação não ocorre com muita frequência (é claro, os dados também devem ser adequados para compactação).
Como o cache lida com a fragmentação?
Observe que a fragmentação da memória e a coleta de lixo são apenas um problema para caches que suportam objetos de dados de tamanhos diferentes. A fragmentação não é um problema porque não ocorre se todos os objetos tiverem o mesmo tamanho. Sempre vale a pena tentar evitar a fragmentação, embora nem sempre seja possível.
Se for necessário lidar com a fragmentação, é provável que esteja interessado em evitar buracos na memória cache alocada. Essas falhas podem levar à condição de cheio, mesmo se o cache estiver meio vazio, porque não há um único bloco de memória que seja grande o suficiente para conter um objeto solicitado. Em
Indy , a coleta de lixo era necessária para o cache de textura. Muitas texturas pequenas compartilhavam o cache com algumas texturas grandes. As pequenas texturas (se não coletadas) se espalhariam uniformemente no cache, efetivamente bagunçando todo o cache, de forma que nenhuma textura grande pudesse ser baixada.
Felizmente, um cache de textura é especialmente adequado para coleta de lixo porque o único cliente que mantém um ponteiro para uma textura é o renderizador. Portanto, você só tem um cliente informando sobre as texturas movidas. A movimentação é necessária para preencher os buracos que vão surgindo durante o uso do cache. A abordagem é bastante simples. Procure no cache, começando no final, uma textura que caiba em um buraco. Ao fazer isso, o espaço no final do cache é liberado, enquanto as lacunas no início do cache são preenchidas. Para fazer isso de forma eficiente, pesquise uma correspondência para cada ou (como foi feito em
Indy) têm um segundo encadeamento usando o tempo de CPU não utilizado de outra forma para navegar pelo cache e limpá-lo. Usar um segundo encadeamento reforça o uso de semáforos para garantir a sincronização adequada entre os encadeamentos, mas isso está fora do assunto e pertence ao adorável campo da programação paralela.
Como determinar o objeto mais antigo em um cache?
Esse problema está estreitamente ligado ao protocolo de acesso básico usado com um cache porque a única entrada disponível para resolver esse problema é o tempo de um Lock () ou Touch (); chamada, desde que nenhuma informação de envelhecimento seja gravada no objeto em cache durante o uso.
- Encontre o objeto mais antigo usando um algoritmo LRU (usado recentemente). Esses algoritmos criam uma lista classificada de objetos em cache. Sempre que um objeto é usado, ele é movido para o topo da lista. Quando um objeto é usado pela primeira vez, ele é adicionado à lista, caso contrário, ele apenas é movido de sua posição anterior. Observe que isso pode produzir resultados incorretos para Lock (); e desbloquear (); protocolo, já que você toma o tempo de travamento como base e não o último tempo de uso. Esse problema não ocorre quando você usa o Touch (); protocolo, porque você tem uma base correta.
- Outra opção é usar carimbos de idade. Sempre que você usa um objeto, você atualiza um carimbo de idade embutido em um objeto. O número do quadro atual é um bom valor. Quando você precisar limpar uma linha de cache, pesquise todos os objetos em cache (o que só é recomendado, quando você tem um cache pequeno) para determinar o mais antigo.
Observe que a estampagem pode ser feita durante Touch (); liga ou mesmo com o Lock (); e desbloquear (); esquema. Nesse caso, você precisará gravar o carimbo de idade em um campo designado do objeto em cache toda vez que for usado.
Dicas para executar caches
Depois que o cache estiver em execução, você deve reservar um tempo e criar um perfil dele. Tenha uma ideia da quantidade de dados que passam e determine por que eles são solicitados. Descubra mais sobre os padrões de acesso. Essas informações podem ser usadas para redimensionar o cache (sim, pode ser muito grande). Em quase todos os caches, existem dois recursos que determinam a condição "cheia". O cache pode ficar sem espaço de armazenamento. Nesse caso, a memória alocada para ele precisa ser aumentada. Por outro lado, o cache pode ficar sem linhas de cache livres. Não fará sentido, neste caso, aumentar o tamanho do armazenamento, se o cache não tiver meios para reter as informações para gerenciar o espaço extra. Além disso, se você descobrir que o espaço de armazenamento do seu cache é muito grande e você reduzi-lo, também pode acabar usando menos linhas de cache. Ao criar o perfil dos caches, esteja ciente das situações reais de jogo. O estresse colocado em um cache de textura é muito diferente quando você usa uma câmera de depuração veloz em vez das câmeras de jogo reais.
Para caches complexos, use muitos, muitos asserts (); para ajudá-lo a verificar a consistência de seu novo cache. Às vezes, alguma programação errada pode fazer você acreditar que está tudo bem até um ponto no final do jogo; como quando seu cache começa a retornar ponteiros para dados, que não pertencem ao objeto correto.
Por último, implemente serviços LRU e FREELIST separados porque você precisará deles novamente. Alguém poderia argumentar que um módulo de cache abstrato seria de algum benefício, mas pelo menos em
Indy , cada cache tinha suas próprias características e casos especiais minúsculos, o que impedia essa abordagem.
Usando um Kernel de Memória Virtual
A etapa final que demos na
Indyestava implementando um kernel de memória virtual para código e dados somente leitura. Esta decisão foi tomada porque o código para uma versão de lançamento chegou muito perto da marca de um megabyte. Comparado com o total de quatro megabytes que o N64 não expandido tem a oferecer, isso era simplesmente demais. Estritamente falando, um kernel de memória virtual representa apenas outro método de armazenamento em cache. É claro que se explora as possibilidades do processador devido ao uso de tabelas de mapeamento de página e da unidade de gerenciamento de memória. Outra coisa boa sobre o uso de kernel é que não há necessidade de dividir o código em várias seções de sobreposição, o que era comum na primeira geração de jogos N64. A sobreposição é uma técnica perigosa para reduzir o tamanho do código. O vinculador coloca módulos mutuamente exclusivos no mesmo espaço de endereço físico. Isto'
Claro, você cometerá erros com esse esquema (simplesmente porque existe o potencial para cometer erros), e ele não dá resultados muito bons. No entanto, como um kernel de memória virtual manterá apenas as páginas de código na memória, que estão realmente sendo usadas, você terá o benefício de sobrepor o código gratuitamente. Muitos módulos também se dividem em duas seções: uma para inicialização e outra para atualizar objetos. Após a inicialização do mecanismo, um kernel de memória virtual descarta o código de inicialização automagicamente, com base no tamanho da página virtual selecionada.
Visualizar anexo 199447
Um kernel também pode fornecer e ajudá-lo a depurar seu programa. É possível detectar acessos de gravação ao código e dados somente leitura. Além disso, o uso de um espaço de endereço virtual exclusivo distingue ainda mais os dados dos endereços. Recursos de memória mapeada também podem ser implementados, no entanto, isso não foi feito em
Indy .
Um kernel de memória virtual consiste em dois componentes principais (cf. fig. 6). Uma tabela de página descreve qual página virtual é mapeada para qual página física na memória, se é que está mapeada. Há uma entrada na tabela de páginas para todas as páginas virtuais conhecidas. Uma página geralmente é um bloco de 4096 bytes. A CPU tem um TLB de 32 entradas (cache de tradução à parte) no chip. Este TLB mapeia até 32 páginas virtuais para suas contrapartes físicas. Você deve configurar um mapeamento global (isto é, espaço de endereço completo) para cobrir acessos válidos de leitura / gravação à memória. No entanto, as 31 entradas restantes podem ser usadas para mapear páginas de código de 4 K. Claro, esses 31 mapeamentos não são suficientes. Portanto, a CPU emite um IRQ de recarga sempre que um mapeamento é desconhecido para o cache TLB. Uma rotina de montagem muito curta busca as informações de mapeamento corretas da tabela de página externa e as carrega em uma entrada TLB aleatória. Esta estratégia aleatória não é a melhor, mas também não é a pior e é fácil de implementar. Na verdade, a CPU MIPS fornece até mesmo um comando de montagem LoadToRandomTLBEntry.
No entanto, quando a CPU encontra uma página virtual não mapeada (ou seja, marcada como inválida), ela emite um IRQ de página inválida. Neste ponto, o software kernel precisa determinar qual página limpar da memória física (usando um algoritmo LRU muito, muito rápido, é claro), invalidar os bits válidos dessa página, baixar a nova página de código da ROM e marcar a página solicitada como sendo válido após a atualização da entrada TLB responsável por aquela página. s também não é o pior e é fácil de implementar. Na verdade, a CPU MIPS fornece até mesmo um comando de montagem LoadToRandomTLBEntry. No entanto, quando a CPU encontra uma página virtual não mapeada (ou seja, marcada como inválida), ela emite um IRQ de página inválida. Neste ponto, o software do kernel precisa determinar qual página limpar da memória física (usando um algoritmo LRU muito, muito rápido, é claro), invalidar os bits válidos dessa página, baixar a nova página de código da ROM e marcar a página solicitada como sendo válido após a atualização da entrada TLB responsável por aquela página. s também não é o pior e é fácil de implementar.
Todo esse processo pode parecer assustador, mas, na verdade, não é muito difícil de implementar. O software do kernel tem, no geral, cerca de 1000 linhas de instruções de montagem MIPS. É preciso cavar fundo no manual do processador, mas vale a pena o esforço. Claro, tentamos rodar
Indy com apenas 64k de código, que funcionou bem, mas muito lento. No final, Indy usou ~ 400k de memória física de código, liberando cerca de 550k.
Conclusão
Para resumir este artigo:
- Mesmo que alguns métodos ganhem uma quantidade considerável de memória, nenhum método sozinho ganha o que você precisa.
- A combinação de métodos faz a diferença. É claro que se deseja lidar com os grandes pedaços primeiro.
- Organizar seus dados com considerações de espaço em mente desde o início é melhor do que realizar uma programação de emergência no final.
- O cache funciona melhor do que o esperado, especialmente quando você armazena recursos em cache em pontos centrais (ou seja, lidando com texturas em apenas um lugar).
- O armazenamento em cache também ajuda a manter os dados locais e, portanto, aumenta o desempenho. Quanto menos dados a CPU tiver que lidar, melhor.
- Não tenha medo de fazer um trabalho de baixo nível. Pelo menos em consoles você ainda pode fazer isso!
- Mesmo com a próxima geração de consoles, os problemas apresentados aqui ainda são válidos (se não mais importantes), e com o ARAM do Gamecube, há algo para fazer o download…
To be continued...