Memorias.

1. Esta entrada está inspirada por la colisión reciente de tres lineas de información:

La primera la desarrollo un poco más:

Recuerdo que antes de embarcarme en la aventura de la patente, cómo no tenía muy claro si ir adelante con ella, simplemente intentar publicar el resultado o no hacer nada y que la invención quedase durmiente en un cajón, me reuní con varios expertos, algunos de ellos investigadores que ya habían patentado, e incluso algunos, licenciado a multinacionales algunos de sus inventos.

Los investigadores / inventores somos como los montañeros y nos ayudamos dentro de las posibilidades de cada uno (obviamente respetando los eventuales NDA, si existiesen o cualquier otro tipo de intereses similares). Por ello todos con los que pude contactar fueron accesibles y la interlocución fue buena. En otros casos (investigadores de fuera de España), el establecer contacto fue más complicado, por cuestiones de spam / e-mail, pero cuando lo conseguí establecer la interlocución fue buena también. Por otra parte yo fui honesto con todos a los que contacté (no me gusta dar gato por liebre, aunque el no hacerlo pueda perjudicarme) y a todos les comuniqué sobre la posibilidad de patentar los resultados de mi investigación antes de pedirles información.

En una de estas reuniones, mi interlocutor, que pese a su apretada agenda muy amablemente accedió a recibirme, cuando le comenté (en realidad con bastante poco detalle, de manera muy abstracta, tal y como me habían recomendado otros expertos en anteriores reuniones; seguramente si hubiese sido más informativo hubiese obtenido también más información) cual era el problema que resolvía mi algoritmo, me comentó muy en abstracto, sin conocer  el tipo de grafos para los que mi algoritmo tenía aplicaciones,  que el problema que éste resolvía podría tener posibles aplicaciones en memorias de computadores (entiendo que no necesariamente de supercomputadores). Como todas las aplicaciones que yo conocía (no se si supuestas o reales) eran más bien relacionadas con enrutamiento en redes de interconexión, me sorprendió este comentario.

Antes termino esta introducción reseñando su consejo sobre si ir adelante con la patente o no.  Repito que el no tenía conocimiento en detalle sobre mi invención. Sólo quería transmitirme su experiencia  con las patentes (él, según me comentó, pese a licenciar, no había ganado dinero; tampoco le importaba pues ya se sentía satisfecho con ver que sus invenciones tenían aplicaciones prácticas reales). Pues bien, su consejo fue que no me embarcase en una patente: es algo caro, de por vida (a  mi edad al menos)  y de dudosa rentabilidad. Aunque, según mi experiencia unos años después, creo que tiene razón y que fue un buen consejo, aunque parezca paradójico, de momento no me arrepiento de haberme embarcado. No sé si cambiaré de opinión dentro de unos meses o años.

La segunda línea informativa, son mis últimas entradas sobre Digrafos de Cayley (tituladas Cuando el tamaño del IAS queda fijo). Todavía sigo pensando (aunque sigo con nulo tiempo para investigar sobre ello) en los problemas planteados allí.

La tercera ha sido una

entrada en otro blog  sobre un reciente descubrimiento en hardware de memorias de computador. Realmente lo que me ha llamado la atención  ha sido la fotografía.

2. Todo esto me ha hecho dedicarle un poco de tiempo a buscar la intersección entre Dispositivos de Memoria (tema sobre el que sé muy poco) y Dígrafos de Cayley.

En realidad, finalmente no he encontrado mucho, desde el punto de vista  cuantitativo. Sólo este antiguo paper de los ochenta, de dos investigadores de los Centros de Investigación  de la Philips, dónde argumentan que la memoria de Von Neuman no es más que una de las posibles implementaciones de una idea más general: la memoria dónde el espacio de direcciones es un Grafo de Cayley (en la arquitectura Von Neuman sería de un grupo cíclico).  Parece interesante, pero pese al así llamado  cuello de Botella de Von Neuman, y pese a que el paper tuvo algunas ctias (ver la página web de uno de los investigadores, donde en una lista de varios papers que lo citan aparece este paper y otro más reciente de 2009), y ambos investigadores tienen varias patentes (ver aquí también), parece que no prosperó la idea.

En relación con nuestra entrada del pasado mes de marzo sobre los Dígrafos de Cayley de Grupos Cuaternios generalizados y su reducción, a efectos de conteo a Digrafos de Cayley de Grupos Dihedricos  en el primer paper citado me ha llamado la atención lo que dicen en la conclusión:

In this paper we hace considered the three units of the Von Neumann computer as a whole and highlighted the Hidden Group structure of the address space. We hac shown that when the integer addition law is used to manipulate addresses, this space is a cyclic group and memory is seen as a linear array. We showed that when another group law is performed in the address arithmetic unit, the memory graph is a Cayley Graph of that group.

A hypercubic memory was presented as an illustration, and the use of a dihedral group of adresses enables to compose plane transformations without any matrix multiplication.

The connection with abstract models of computation could be stablished, having in mind the work of Max Garzon (hoy por lo visto experto en Bioinformática) who defined an extension of Turing Machines called Cayley Machines (en este artículo de 1987). He noticed that the right and left moves of a Turing Machine define a single direction of motion with direct and inverse orientation. This provides the tape with an infinite group structure.   He then propose to increase the number of moves of the abstract machine tape; the forward and backward directions in each avalaible move give a group structure to the tape. 

También un extracto de un abstract, que no tiene nada que ver con los Digrafos de Cayley pero que habla de una aplicación en la que pienso cuando escribo sobre estos temas:

Motivated by two real world applications: assigning computer memory network and robotic navigation, the notion of metric dimension was introduced separately by Slater (1975) and Harary and Melter
(1976).

Bueno, ya tiene que ver. Cómo siempre, si bien se conoce la complejidad computacional de este problema en el caso general, nadie habla sobre su complejidad computacional en (Dí)grafos de Cayley. Encuentro este fenómeno, que de manera invariante se repite siempre, sea quien sea el que escribe el artículo, es realmente curioso. Vamos a ver: digo yo que si empiezas el paper comentando que el problema general es NP-Hard  y luego te restringes ha una clase más específica de (Dí)grafos, los de Cayley, el lector seguramente se preguntará sobre la Complejidad Computacional de estos casos más específicos ¿ no?.  Pues como si no. Por alguna misteriosa causa que no alcanzo a comprender, nunca se comenta sobre ello…:-). Coño (y pido perdón por la palabra), si sigue siendo NP-Hard, que se diga; si es más fácil que se diga igualmente; y si no se sabe la complejidad del caso restringido, pues tanto de los mismo. ¿ Es tan difícil comprender esto ?

En fin, relacionado pero de manera más indirecta, esta presentación más reciente sobre un sistema HPC. Aquí en formato de paper.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: