Browse Prior Art Database

OPTIMIZATION OF MESSAGE MEMORY

IP.com Disclosure Number: IPCOM000008819D
Original Publication Date: 1998-Sep-01
Included in the Prior Art Database: 2002-Jul-16
Document File: 2 page(s) / 116K

Publishing Venue

Motorola

Related People

Sanjay Choudhary: AUTHOR [+2]

Abstract

To obtain low cost and high battery life, today's paging products are designed with highly optimized software operating at low CPU bus speeds, optimized RAM use and minimal ROM. With much low-level message protocol decoding and formatting performed in a micro-controller, along with the increased speed of newer protocols, pager firmware frequently empha- sizes the optimization of real-time message processing. Providing fast storage for messages of varying sizes while minimally impacting ROM use, node-based dynamic linked list message storage has become the preferred storage algorithm.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

0 M

MOTOROLA Technical Developments

OPTIMIZATION OF MESSAGE MEMORY

by Sanjay Choudhary and Charlie Mellone

OVERVIEW

    To obtain low cost and high battery life, today's paging products are designed with highly optimized software operating at low CPU bus speeds, optimized RAM use and minimal ROM. With much low-level message protocol decoding and formatting performed in a micro-controller, along with the increased speed of newer protocols, pager firmware frequently empha- sizes the optimization of real-time message processing. Providing fast storage for messages of varying sizes while minimally impacting ROM use, node-based dynamic linked list message storage has become the preferred storage algorithm.

  Node-based storage algorithms incur an overhead due to the node linkage pointers and the resultant last node fragmentation. For example, 32 byte node sizes with 2 byte next-node pointers per node result in an overhead of more than 6% of message memory just for the pointers. For doubly-linked lists, this overhead approaches 15%. Tbis does not even include the over- head caused by a message tilling only a portion of the last node which, on average, wastes an additional one half of a node.

NODE DE-FRAGMENTATION

  Fragmentation of a message naturally occurs in a node-based system where messages of varying sizes need to be stored. It begins once a message is deleted and a new message of a different size needs to be stored. Messages can be deleted because memory becomes full or a user deletes a message.

  The Node De-fragmentation realigns all the nodes of a fragmented message in contiguous order. The fol- lowing swapping algorithm can be used to accomplish this reordering.

  In this algorithm, nodes are swapped using a buffer until all the nodes are aligned in contiguous order. For this swapping algorithm to work, the fragmented nodes should be in a doubly linked list. After swapping or moving a node, previous and next node pointers will be updated to the new node address. Since nodes are ;allo- cated to a message using a doubly linked list, it is very easy to locate the next node and update the node point- ers of next and previous.

PROPOSED IMPLEMENTATION

   For just a few hundred bytes of ROM and some additional background processing, the proposed imple- mentation maintains all the initial execution efticien- ties of the node-based approach while reducing mes- sage storage overhead to virtually zero. This is accom- plished by utilizing the same proven doubly-linked list node-based message storage algorithm for initial mes- sage storag...